#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
const long long inf = 1e18;
long long ans = inf;
vector<long long> pref(n);
vector<long long> suff(n);
vector<long long> x(n), y(n);
for (int i = 0; i < n; i++) {
x[i] = a[i];
y[i] = a[i];
}
for (int i = 0; i < n; i++) {
if (i > 0) {
pref[i] = pref[i - 1];
x[i] = max(a[i], a[i - 1] + 1);
}
pref[i] += x[i] - a[i];
}
for (int i = n - 1; i >= 0; i--) {
if (i < n - 1) {
suff[i] = suff[i + 1];
y[i] = max(a[i], a[i + 1] + 1);
}
suff[i] += y[i] - a[i];
}
if (n == 1) {
cout << 0 << '\n';
return 0;
}
for (int i = 0; i < n; i++) {
long long cur = inf;
if (i > 0) {
cur = min(cur, pref[i - 1]);
}
if (i < n - 1) {
cur = min(cur, suff[i + 1]);
}
ans = min(ans, max(pref[i], suff[i]));
}
cout << ans << '\n';
return 0;
}
