#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
ll INF = 1e18;
ll MOD = 1e9 + 7;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ll n;
cin >> n;
vector<ll> s(n);
for (ll i = 0; i < n; i++) {
cin >> s[i];
}
vector<ll> pref(n);
vector<ll> suf(n);
ll x = 0;
ll last = s[0];
for (ll i = 1; i < n; i++) {
if (s[i] + x <= last) {
x = last - s[i] + 1;
last++;
} else {
last = max(last, s[i] + x);
}
pref[i] = x;
}
x = 0;
last = s[n - 1];
for (ll i = n - 2; i >= 0; i--) {
if (s[i] + x <= last) {
x = last - s[i] + 1;
last++;
} else {
last = max(last, s[i] + x);
}
suf[i] = x;
}
ll mx = INF;
for (ll i = 0; i < n; i++) {
mx = min(mx, max(pref[i], suf[i]));
}
cout << mx << endl;
}
