You are given a histogram consisting of $N$ columns of heights $X_1,X_2,\dots ,X_N$, respectively. The histogram needs to be transformed into a roof using a series of operations. A roof is a histogram that has the following properties:

• A single column is called the top of the roof. Let it be the column at position $i$.
• The height of the column at position $j$ $(1\le j\le N)$ is $h_j=h_i-|i-j|$.
• All heights $h_j$ are positive integers.

An operation can be increasing or decreasing the heights of a column of the histogram by $1$. It is your task to determine the minimal number of operations needed in order to transform the given histogram into a roof.

Input Specification

The first line of input contains the number $N$ $(1\le N\le {10}^5)$, the number of columns in the histogram. The following line contains $N$ numbers $X_i$ $(1\le X_i\le {10}^9)$, the initial column heights.

Output Specification

You must output the minimal number of operations from the task.

Scoring

In test cases worth 60% of total points, it will hold $N\le 5000$.

Sample Input 1

4
1 1 2 3

Sample Output 1

3

Explanation for Sample Output 1

By increasing the height of the second, third, and fourth column, we created a roof where the fourth column is the top of the roof.

Sample Input 2

5
4 5 7 2 2

Sample Output 2

4

Explanation for Sample Output 2

By decreasing the height of the third column three times, and increasing the height of the fourth column, we transformed the histogram into a roof. The example is illustrated below.

Sample Input 3

6
4 5 6 5 4 3

Sample Output 3

0