#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 998244353;
void solve() {
int n; cin >> n;
vector<int> a(n+2);
rep(i, 1, n+1)cin >> a[i];
vector<int> inc(n+1), dec(n+2);
inc[1] = a[1], dec[n] = a[n];
int mx1 = a[1], mx2 = a[n];
rep(i, 2, n+1) {
inc[i] = max(a[i], mx1+1);
mx1 = max(mx1, inc[i]);
}
rep(i, n, 1) {
dec[i] = max(a[i], mx2+1);
mx2 = max(mx2, dec[i]);
}
vector<int> p(n+2), s(n+2);
rep(i, 2, n+1) {
int x = inc[i]-a[i];
if (x <= inc[i-1]-a[i-1])p[i] = 0;
else p[i] = x-inc[i-1]+a[i-1];
p[i] += p[i-1];
}
rep(i, n, 1) {
//cout << i << " ";
int x = dec[i]-a[i];
if (x <= dec[i+1]-a[i+1])s[i] = 0;
else s[i] = x-dec[i+1]+a[i+1];
s[i] += s[i+1];
}
//for (auto i: inc)cout << i << " ";
//cout << nl;
//for (auto i: dec)cout << i << " ";
//cout << nl;
int res = min(p[n], s[1]);
//cout << p[n] << " " << s[1] << nl;
rep(i, 1, n+1) { // increase till i, decrease after
int x = max(dec[i], inc[i]);
int sm = p[i-1]+s[i+1];
sm += max(0ll, x-a[i]-(inc[i-1]-a[i-1]+dec[i+1]-a[i+1]));
res = min(res, sm);
//if (sm == 0)cout << i << nl;
}
cout << res << nl;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
