#include<bits/stdc++.h>
using namespace std;
#define int long long
void test_case(){
int n;
cin >> n;
int a[n], a1[n];
for(int i = 0; i < n; i++) {cin >> a[i]; a1[i] = a[i];}
int pre[n]={}, suf[n]={};
for(int i = 1; i < n; i++){
if(a[i]<=a[i-1]) pre[i] = max(pre[i-1], a[i-1]-a[i]+1);
else pre[i] = pre[i-1];
a[i] = max(a[i], a[i-1]+1);
}
// for(int i = 0; i < n; i++) cout << pre[i] <<" ";
// cout << endl;
for(int i = 0; i < n; i++) {a[i] = a1[i];}
int ans =1e9;
for(int i = n-2; i >=0; i--){
// cout << a[i] <<" "<< a[i+1]<<endl;
if(a[i]<=a[i+1]) {suf[i] = max(suf[i+1], a[i+1]-a[i]+1);}
else suf[i] = suf[i+1];
a[i] = max(a[i], a[i+1]+1);
//cout << a[i]<< " ";
}
//cout << endl;
// for(int i = 0; i < n; i++) cout << suf[i] <<" ";
// cout << endl;
for(int i = 0; i < n; i++){
int mx = max(pre[i], suf[i]);
ans = min(ans, mx);
}
cout << ans;
}
signed main(){
int t;
t=1;
while(t--) test_case();
}
