Description

给定一个由 N 个柱子组成的直方图，其高度分别为 $X_1, X_2, \ldots, X_N$。需要通过一系列操作将直方图转换为屋顶。屋顶是具有以下性质的直方图：

• 单个柱子称为屋顶的顶点。设其为位置 $i$ 的柱子。
• 位置 $j\ (1 \leq j \leq N)$ 的柱子的高度为 $h_j = h_i - |i - j|$。
• 所有高度 $h_j$ 都是正整数。

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

Input Format

输入的第一行包含一个数 $N\ (1 \leq N \leq 10^5)$，表示直方图中的柱子数量。

接下来的行包含 $N$ 个数 $X_i\ (1 \leq X_i \leq 10^9)$，表示初始的柱子高度。

Output Format

你必须输出完成任务所需的最小操作次数。

4
1 1 2 3

3

5
4 5 7 2 2

4

6
4 5 6 5 4 3

0

Hint

在占总分 60% 的测试用例中，将满足 $N \leq 5000$。

第一个测试用例的说明： 通过增加第二、第三和第四个柱子的高度，我们创建了一个屋顶，其中第四个柱子是屋顶的顶点。

第二个测试用例的说明： 通过将第三个柱子的高度减少三次，并增加第四个柱子的高度，我们将直方图转换为屋顶。例子如下图所示。

题面翻译由 ChatGPT-4o 提供。