题意：海平面每天高度会变化，一个人会在每天海平面的位置刻下一道痕迹（如果当前位置没有已经刻划过的痕迹），并且记录下当天比海平面高的痕迹有多少条，记为a[i]。让你最小化每天比海平面低的痕迹条数之和。
贪心，使得痕迹条数尽可能小。
考虑处理出每天痕迹条数的数组f[i]的最小可能值。
满足几个约束即可，f[i]>=f[i-1]，f[i]>=a[i]+1，f[i]>=f[i+1]-1。前后扫两遍就可以处理出f数组，然后就可以轻松统计答案了。
#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[100005],f[100005];
int main(){
//freopen("d.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
f[i]=max(f[i-1],a[i]+1);
}
for(int i=n;i>=1;--i){
f[i]=max(f[i+1]-1,f[i]);
}
long long ans=0;
for(int i=1;i<=n;++i){
ans+=(long long)(f[i]-1-a[i]);
}
printf("%lld
",ans);
return 0;
}