题目描述

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.

题目翻译

给定一个由 N 列高度 $X_1$ , $X_2$ , … $X_N$ , 组成的直方图， 分别。 需要使用一系列操作将直方图转换为屋顶。 屋顶是具有以下属性的直方图：

一根柱子称为屋顶的顶部。 让它成为位置 i 的列。

位置 j (1 ≤ j ≤ N) 处的列高度为$ h_j = h_i- |i - j|$
所有高度 $h_j$是正整数。

一个操作可以将直方图的一列的高度增加或减少 1。您的任务是确定将给定直方图转换为屋顶所需的最少操作数。

输入格式

The first line of input contains the number N (1 ≤ N ≤ $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.

样例 #1

样例输入 #1

4
1 1 2 3

样例输出 #1

3

样例 #2

样例输入 #2

5
4 5 7 2 2

样例输出 #2

4

样例 #3

样例输入 #3

6
4 5 6 5 4 3

样例输出 #3

0

提示

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

Clarification of the first test case: ​通过增加第二、第三和第四列的高度， 我们创建了一个屋顶，其中第四列是屋顶的顶部。

Clarification of the second test case: ​通过将第三列的高度降低三次，以及 增加第四列的高度，我们将直方图转换为屋顶。 例子是 如下图所示。