题目描述

与此同时，另一边……

神秘商人的店铺中售卖$N$个物品，价格分别为$A_1, A_2, \cdots , A_N$，现在，她想知道，如果想要在不改变这些物品顺序的情况下，需要修改几次才可以使这些物品的价格形成一个公差为1的等差数列。

P.S：因为神秘商人的生意很差，所以有时也会将物品不要钱甚至倒贴钱赠送给买家，即修改后的$A_i$可能$\le 0$

输入格式

第 $1$ 行，$1$ 个整数 $N$。

第 $2$ 行，$N$ 个整数 $A_1, A_2, \cdots , A_N$。

输出格式

$1$ 个整数，表示最少修改的次数

样例

3
2 1 3

2

数据范围

• 对于$40\%$ 的数据，$N \leqslant 1000$
• 对于$100\%$的数据，$N \le 10^{5}$， $1 \le A_i \le 10^{6}$