#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<ll, ll>
typedef long long ll;
const ll MOD = 1000000007LL;
const ll INF = 1e15;
using namespace std;
ll n, a[200010], pre[200010], suf[200010];
ll ans1[200010], ans2[200010], ans;
int main() {
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(0);
cin >> n ;
for (int i = 1; i <= n; i++) cin >> a[i];
pre[1] = suf[n] = 0;
for (int i = 2; i <= n; i++) pre[i] = max(0LL, pre[i-1]+a[i-1]+1-a[i]);
for (int i = n-1; i >= 1; i--) suf[i] = max(0LL, suf[i+1]+a[i+1]+1-a[i]);
ans1[1] = pre[1]; ans2[n] = suf[n];
for (int i = 2; i <= n; i++) ans1[i] = ans1[i-1]+max(0LL, pre[i]-pre[i-1]);
for (int i = n-1; i >= 1; i--) ans2[i] = ans2[i+1]+max(0LL, suf[i]-suf[i+1]);
// for (int i = 1; i <= n; i++) cout << a[i] << ' ' << pre[i] << ' ' << suf[i] << ' ' << ans1[i] << ' ' << ans2[i] << "\n";
ans = INF;
for (int i = 1; i <= n; i++) {
ans = min(ans, max(ans1[i], ans2[i]));
}
cout << ans << "\n";
return 0;
}
/*
*/
