1.5 \(s / 128\) \(MB / 140\) points

You are given a histogram consisting of \(N\) columns of heights \(X\) {1}{ }, \(X\) {2}{ }, ... \(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 ≤ \(j\) ≤ \(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.

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

The first line of input contains the number \(N\) (1 ≤ \(N \le 10\) ^{5}{ }), the number of columns in the

histogram.
The following line contains \(N\) numbers \(X\) {i}{ } (1 ≤ \(X\) {i}{ } ≤ 10 ^{9}{ }), the initial column heights.

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

생성자가 기록되지 않았습니다.

출처 COCI 2017/2018 Contest 4