Problem Description

You are given a histogram consisting of \( N \) columns of heights \( X_1, X_2, \ldots, 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 \leq j \leq 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 Format

The first line of input contains the number \( N \) ( \( 1 \leq N \leq 10^5 \) ), the number of columns in the histogram.

The following line contains \( N \) numbers \( X_i \) ( \( 1 \leq X_i \leq 10^9 \) ), the initial column heights.

Output Format

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

Sample Input and Output

Sample Input #1

4
1 1 2 3

Sample Output #1

3

Sample Input #2

5
4 5 7 2 2

Sample Output #2

4

Sample Input #3

6
4 5 6 5 4 3

Sample Output #3

0

Notes

In test cases worth 60% of total points, it will hold \( N \leq 5000 \).

Clarification of the first test case: 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.

Clarification of the second test case: 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.

见题面 Input 部分

见题面 Output 部分