Roof

Interview

Time limit1.5sMemory limit128 MB

Summary

Given N column heights, pick a peak position and height so the roof shape h_j = peak - |peakpos - j| is positive everywhere, minimizing total absolute changes.

Level: Medium6 of 10
Topics: Array, Prefix sum, Math, Implementation
Solved: No attempts yet

Problem

A histogram consists of $N$ columns whose heights are $X_1, X_2, \ldots, X_N$ . You want to turn the histogram into a roof by performing operations. A roof is a histogram with the following properties.

One column is the top of the roof. Let its position be $i$ .
The column at position $j$ ( $1 \le j \le N$ ) has height $h_j = h_i - |i - j|$ .
Every height $h_j$ is a positive integer.

One operation increases or decreases the height of a single column by $1$ . Find the minimum number of operations needed to turn the given histogram into a roof.

Input

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

The second line contains $N$ numbers $X_i$ ( $1 \le X_i \le 10^9$ ), the initial column heights, separated by spaces.

Output

Print the minimum number of operations.

Hint

In the first example, raising the second, third, and fourth columns by $1$ each creates a roof whose top is the fourth column.

In the second example, lowering the third column by $3$ and raising the fourth column by $1$ turns the histogram into a roof. The picture below shows the second example.

The transformation in the second example

Examples3

Example 1
Input
```
4
1 1 2 3
```
Expected output
```
3
```
Example 2
Input
```
5
4 5 7 2 2
```
Expected output
```
4
```
Example 3
Input
```
6
4 5 6 5 4 3
```
Expected output
```
0
```