#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <tuple>
#define int long long
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using piii = tuple<int,int,int>;
#define endl '\n'
#define f first
#define s second
#define all(x) begin(x),end(x)
signed main(){
int n;cin >>n;
vector<int> vc = {0};
vector<int> pref = {0};
vector<int> suff = {0};
for(int i{};i <n;i++){
int g;cin >> g;
vc.emplace_back(g);
}
vc.emplace_back(0);
for(int i{1};i <= n;i++){
pref.emplace_back(pref.back()+max(vc[i-1]-vc[i]+1ll,0ll));
}
for(int i{n};i > 0;i--){
suff.emplace_back(suff.back()+max(vc[i+1]-vc[i]+1ll,0ll));
}
reverse(all(suff));
int ans = 1e9+10;
for(int i{1};i <= n;i++){
//cout << pref[i] << " " << suff[i-1] << endl;
ans = min(ans,max(pref[i],suff[i-1]));
}
cout << ans;
}
