考场降智，对于带 0 的数据打了一个不知道是什么鬼东西的算法，还调挂了（

---

对于这些方块，我们把它们看成是 \(n\) 个平面上的点 \((i,a_i)\)，那么样例 \(1\) 就长这样：

样例 \(2\) 就长这样：

我们发现就可以转换为这样一个问题：找到若干对直线 \(y1_i= x +b1_i\) 和 \(y2_i=-x +b2_i\)，并使得 \(\sum (b1_i+b2_i)\) 最小（即截距之和最小），最后答案就是：
\(\sum \lceil\frac{(b1_i+b2_i)}{2}\rceil\) 。

长得有点像线性规划？（考场上就一直往线性规划上想，最后只有 45 pts），但其实没有那么复杂。

考虑这样一个结论：两对直线 \(y1_a,y2_a\) 和 \(y1_b,y2_b\) ，其中第一对直线交点 \(x_1\) 小于第二对直线交点 \(x_2\)，若 \(y2_a\) 与 \(y1_b\) 的交点的 \(y\) 坐标 \(\geq 0\)，则这两对直线可以合并成一对直线 \(y1_c=x+max(y1_a,y1_b),y2_c=-x+max(y2_a,y2_b)\)。

为什么？来感性理解一下，看这张图：

如图，两对黑色的直线（这里为了好看，画成射线）是原本的两队直线，红色（\(HR\) 和 \(HT\)）的是合并后的一对直线，我们发现，这样的一对橙色线可以完美盖住两对黑色线的部分，还多盖住了标出的矩形的位置；并且，我们多画几个就会发现总是满足：\(\frac{b1_c+b2_c}{2}\leq \frac{b1_a+b2_a}{2}+\frac{b1_b+b2_b}{2}\)，极限情况是交点在 \(x\) 轴上，此时 \(\frac{b1_c+b2_c}{2}= \frac{b1_a+b2_a}{2}+\frac{b1_b+b2_b}{2}\)。

那么只有有两对这样满足条件的直线，合并就一定更优。

---

具体做法有很多中，这里提供一个简单的做法：

我们发现可合并的直线对一定是相邻的，那么就可以这样：首先开一个栈记录从前向后的直线对。对于每个点，我们把它单独视为一个区间，两条直线分别为：\(y1_i=x+a_i-i\) 和 \(y2_i=-x+a_i+i\)。每新加入一个区间（点），从栈顶向下一直与可合并的区间合并，然后将合并完的新区间放到栈顶。最后扫一遍栈统计答案就行了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define rg register
#define inf 0x3f3f3f3f3f3f3f3f
#define ll long long
inline int read(){
	rg int ret=0,f=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)){ret=ret*10+ch-48;ch=getchar();}
    return f?-ret:ret;
}
struct node{
	ll b1,b2;
}st[1000005],now;  //开栈。 
int n,top;
ll a[1000005],ans;  
inline node merge(node a,node b){
	node ret;
	ret.b1=max(a.b1,b.b1); ret.b2=max(b.b2,a.b2);
	return ret;
} //合并直线（区间）。 
signed main(){
	n=read();
	for(rg int i=1;i<=n;++i){
		a[i]=read(); now.b1=a[i]-i; now.b2=a[i]+i;  //将新加入的点视为一个已处理好的区间。 
		while(((st[top].b2+now.b1)>>1>=0)&&top) 
			now=merge(st[top--],now);   //不断 merge 并 pop。 
		st[++top]=now;    
	}
	while(top){
		if((st[top].b2+st[top].b1)&1) ans+=(st[top].b2+st[top].b1+1)>>1;
		else ans+=(st[top].b2+st[top].b1)>>1;
		--top;
	} //统计答案。 
	printf("%lld",ans);
	return 0;
}