给你一个由 $N$ 列组成的直方图，各列的高度分别为 $X_1, X_2, \dots, X_N$。你需要通过一系列操作将该直方图转换成一个“屋顶”。屋顶是满足以下性质的直方图：

• 其中一列被称为屋顶的顶部。设其在位置 $i$。
• 位置 $j$ ($1 \le j \le N$) 处的列高度为 $h_j = h_i - |i - j|$。
• 所有高度 $h_j$ 均为正整数。

一次操作可以将直方图中某一列的高度增加 $1$ 或减少 $1$。

你的任务是求出将给定的直方图转换成屋顶所需的最少操作次数。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 10^5$)，表示直方图的列数。

第二行包含 $N$ 个整数 $X_i$ ($1 \le X_i \le 10^9$)，表示各列的初始高度。

输出格式

输出转换成屋顶所需的最少操作次数。

数据范围

对于 $60\%$ 的数据，满足 $N \le 5000$。

样例

输入样例 1

4
1 1 2 3

输出样例 1

3

输入样例 2

5
4 5 7 2 2

输出样例 2

4

输入样例 3

6
4 5 6 5 4 3

输出样例 3

0

说明

样例 1 说明：通过将第二、第三和第四列的高度增加，我们得到了一个以第四列为顶部的屋顶。

样例 2 说明：通过将第三列的高度减少三次，并将第四列的高度增加一次，我们将直方图转换为了一个屋顶。该过程如下图所示。