record

思路是：造两个序列c,d，c严格递增，d严格递减，且$c_i,d_i>=a_i$，并使$c_i,d_i$最小

然后枚举拐点，设拐点为k，找到$c_1$至$c_k$减$a_1$至$a_k$，$d_k$至$d_n$减$a_k$至$a_n$中的最小值（用了前缀最小值）

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,a[200010],l[200010],r[200010],maxx=-1;
int qzhl[200010],qzhr[200010],ans;
signed main(){
	cin>>n;
	qzhl[1]=-1e17,qzhr[n]=-1e17,ans=1e17;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]>l[i-1]) l[i]=a[i];
		else l[i]=l[i-1]+1;
	}
	for(int i=n;i>=1;i--){
		if(a[i]>r[i+1]) r[i]=a[i];
		else r[i]=r[i+1]+1;
	}
	for(int i=1;i<=n;i++){
		l[i]=l[i]-a[i];
		qzhl[i]=max(qzhl[i-1],l[i]);
	}
	for(int i=n;i>=1;i--){
		r[i]=r[i]-a[i];
		qzhr[i]=max(qzhr[i+1],r[i]);
	}
	for(int i=1;i<=n;i++){
		ans=min(ans,max(qzhl[i],qzhr[i]));
	}
	cout<<ans;
	return 0;
}