#include <bits/stdc++.h>
#define ff first
#define ss second
#define N 1000000
typedef long long ll;
const ll NIL = 0;
using namespace std;
ll n, h[N];
pair<ll, ll> dp[2][N];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(ll i = 1; i <= n; i++){
cin >> h[i];
}
for(ll i = 1; i <= n; i++){
if(dp[0][i - 1].ss + h[i - 1] < h[i]){
dp[0][i].ff = dp[0][i - 1].ff;
dp[0][i].ss = 0;
}
else{
dp[0][i].ss = dp[0][i - 1].ss + h[i - 1] + 1 - h[i];
dp[0][i].ff = dp[0][i - 1].ff + (max(NIL, dp[0][i].ss - dp[0][i - 1].ss));
}
}
for(ll i = n; i >= 1; i--){
if(dp[1][i + 1].ss + h[i + 1] < h[i]){
dp[1][i].ff = dp[1][i + 1].ff;
dp[1][i].ss = 0;
}
else{
dp[1][i].ss = dp[1][i + 1].ss + h[i + 1] + 1 - h[i];
dp[1][i].ff = dp[1][i + 1].ff + (max(NIL, dp[1][i].ss - dp[1][i + 1].ss));
}
}
ll ans = 1e18;
for(ll i = 1; i <= n; i++){
ll height = max(dp[0][i - 1].ss + h[i - 1], dp[1][i + 1].ss + h[i + 1]) + 1;
ll many = max(NIL, height - h[i]);
ll u = min(dp[0][i - 1].ss, dp[1][i + 1].ss);
ll v = max(dp[0][i - 1].ss, dp[1][i + 1].ss);
if(many <= v){
ans = min(ans, dp[0][i - 1].ff + dp[1][i + 1].ff - u);
}
else ans = min(ans, dp[0][i - 1].ff + dp[1][i + 1].ff - u + many - v);
}
cout << ans;
}
