#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int main(){
int n;
cin>>n;
vi arr(n);
for(int i = 0; i < n; i++) cin>>arr[i];
int pref[n], suf[n];
vi cpy = arr;
pref[0] = 0;
for(int i = 1; i < n; i++){
if(arr[i] > arr[i-1])
pref[i] = 0;
else{
int to = arr[i-1]+1;
pref[i] = to - arr[i];
arr[i] = to;
}
}
arr = cpy;
suf[n-1] = 0;
for(int i = n - 2; i >= 0; i--){
if(arr[i] > arr[i+1])
suf[i] = 0;
else{
int to = arr[i+1]+1;
suf[i] = to - arr[i];
arr[i] = to;
}
}
int pref_max[n], suf_max[n];
pref_max[0] = pref[0];
for(int i = 1; i < n; i++)
pref_max[i] = max(pref_max[i-1], pref[i]);
suf_max[n-1] = suf[n-1];
for(int i = n-2; i >= 0; i--){
suf_max[i] = max(suf_max[i+1], suf[i]);
}
int ans = 1e9;
for(int i = 0; i < n; i++){
ans = min(ans, max(suf_max[i], pref_max[i]));
}
cout<<ans<<endl;
return 0;
}
