#include <iostream>
#include <vector>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int a[N], d[N], Pre[N], Suf[N], Mx1[N], Mx2[N], d2[N];
signed main(){
int n;
cin>>n;
for (int i=1;i<=n;i++){
cin>>a[i];
Mx1[i] = max(Mx1[i-1] + 1, a[i]);
d[i] = max(0LL, Mx1[i] - a[i]);
Pre[i] = Pre[i-1] + d[i] - min(d[i], d[i-1]);
// cout<<Pre[i]<<' ';
}
// cout<<'\n';
for (int i=n;i>=1;i--){
Mx2[i] = max(Mx2[i+1] + 1, a[i]);
d2[i] = max(0LL, Mx2[i] - a[i]);
Suf[i] = Suf[i+1] + d2[i] - min(d2[i], d2[i+1]);
// cout<<Suf[i]<<' ';
}
// cout<<'\n';
for (int i=n-1;i>=1;i--){
Mx1[i] = max(max(Mx1[i-1], Mx2[i+1]) + 1, a[i]);
d[i] = max(0LL, Mx1[i] - a[i]);
Pre[i] = Pre[i-1] + d[i] - min(d[i], d[i-1]);
Pre[n] = min(Pre[n], max(Pre[i], Suf[i+1]));
// cout<<Mx1[i]<<" "<<d[i]<<" "<<Pre[i]<<'\n';
}
// cout<<'\n';
cout<<Pre[n]<<'\n';
}
