这其实是一个很经典的问题：坐标轴上有一些点，求一个点到它们的距离和最小。众所周知这个选出的点就是所有点的中位数。

于是我们使用树状数组+二分查询中位数：查询左边满足$X_j-j<H_i-i$的$j$的数量，右边$X_j+j<H_i+i$的数量，如果这两个值加起来多于一半那么说明$H_i$估大了，否则估小了，于是可以二分。

查询答案则不难。以左边为例，对于$X_j-j<H_i-i$的$j$贡献是$H_i-i-X_j+j$，否则是其相反数，显然可以树状数组维护。

实现时还要注意一些小细节：

• $H_j$必须是正数，需要设好二分范围。

• 二分中位数时的“一半”应该是$\lceil\frac n 2\rceil$。

代码如下。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int inf=1000100000;

int N;
int X[100005],val[200005],n;
struct BIT{
	int C0[200005];ll C1[200005];
	void chn(int x,int k0,int k1){for(;x<=n;x+=x&-x) C0[x]+=k0,C1[x]+=k1;}
	int qst0(int x){int ans=0;for(;x;x-=x&-x) ans+=C0[x];return ans;}
	ll qst1(int x){ll ans=0;for(;x;x-=x&-x) ans+=C1[x];return ans;}
}Lbit,Rbit;
int Find(int x){
	int L=0,R=n,mid;
	while(L<R){
		mid=(L+R+1)>>1;
		if(val[mid]<=x) L=mid;
		else R=mid-1;
	}
	return L;
}
int main(){
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf("%d",&X[i]),
		val[++n]=X[i]-i,val[++n]=X[i]+i;
	val[++n]=-inf;
	sort(val+1,val+n+1);n=unique(val+1,val+n+1)-val-1;
	
	for(int i=1;i<=N;i++) Rbit.chn(Find(X[i]+i),1,X[i]+i);
	
	ll ans=0x3f3f3f3f3f3f3f3f;
	for(int i=1;i<=N;i++){
		Rbit.chn(Find(X[i]+i),-1,-X[i]-i);
		Lbit.chn(Find(X[i]-i),1,X[i]-i);
		
		int L=max(i,N-i+1),R=inf,mid;
		while(L<R){
			mid=(L+R)>>1;
			if(Lbit.qst0(Find(mid-i))+Rbit.qst0(Find(mid+i))>=(N+1)/2) R=mid;
			else L=mid+1;
		} 
		
		int cntLl=Lbit.qst0(Find(R-i)),cntLr=Lbit.qst0(Find(inf))-cntLl,
			cntRl=Rbit.qst0(Find(R+i)),cntRr=Rbit.qst0(Find(inf))-cntRl;
		ll  sumLl=Lbit.qst1(Find(R-i)),sumLr=Lbit.qst1(Find(inf))-sumLl,
			sumRl=Rbit.qst1(Find(R+i)),sumRr=Rbit.qst1(Find(inf))-sumRl;
		ans=min(ans,(sumLr-sumLl+1LL*(cntLl-cntLr)*(R-i))+(sumRr-sumRl+1LL*(cntRl-cntRr)*(R+i)));
	}
	printf("%lld\n",ans);
}