#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lld long double
vector<ll> policz(int n, vector<ll> arr) {
vector<ll> v(n);
v[0] = 0;
ll ak = arr[0], z = 0;
for (int i = 1; i < n; i++) {
ak = max(ak + 1, arr[i] + v[i-1]);
v[i] = max(v[i-1], ak - arr[i]);
}
return v;
}
int main() {
ios_base::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
int n;
cin >> n;
vector<ll> arr(n);
for (int i = 0; i < n; i++) cin >> arr[i];
vector<ll> l = policz(n, arr);
reverse(arr.begin(), arr.end());
vector<ll> p = policz(n, arr);
reverse(p.begin(), p.end());
ll wyn = 1e18;
for (int i = 0; i < n; i++) wyn = min(wyn, max(p[i], l[i]));
cout << wyn;
}
