#P18870. [HONI 2017/2018 #4] Krov

[HONI 2017/2018 #4] Krov

题目描述

有 NN 根柱子,第 jj 根高 XjX_j。一次操作可以让任意一根柱子的高度增加或减少 11。

你要把柱子变成屋顶形状。选定第 ii 根柱子作为屋顶顶点,设它的最终高度为 hih_i,则其余各柱的最终高度必须满足 hj=hi−∣i−j∣h_j=h_i-|i-j|,并且所有柱子的最终高度都是正整数。

求最少操作次数。

输入格式

第一行一个整数 NN,满足 1≤N≤1051\le N\le10^5。第二行 NN 个整数 X1,…,XNX_1,\ldots,X_N,满足 1≤Xj≤1091\le X_j\le10^9。

输出格式

输出最少操作次数。

部分分

60%60\% 的分值对应 N≤5000N\le5000 的测试。

样例

样例 1

输入

4
1 1 2 3

输出

3

样例 2

输入

5
4 5 7 2 2

输出

4

样例 3

输入

6
4 5 6 5 4 3

输出

0