// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;
#define endl "\n"
#define pb push_back
#define int long long
#define fi first
#define se second
const int N = 3e5 + 5, M = 1e9 + 7, LG = 20;
int n , A[N];
void solve(){
cin >> n;
A[0] = -1e18;
A[n+1] = -1e18;
for (int i=1 ; i<=n ; i++){
cin >> A[i];
}
int p1 = 1 , p2 = n;
int ans = 0;
while(p1 <= p2){
// cout << p1 << ' ' << p2 << ' ';
if (p1 == p2){
int r1 = A[p1-1] - A[p1] + 1 , r2 = A[p2+1] - A[p2] + 1;
// cout << r1 << ' ' << r2 << ' ' << A[p1] << endl;
ans += max(0ll , min(r1 , r2));
break;
}
if (p1 < p2 && A[p1] > A[p1-1]){
p1++;
if (p1 == p2) continue;
A[p1] += ans;
// cout << ans << endl;
continue;
}
if (p2 > p1 && A[p2] > A[p2+1]){
p2--;
if (p1 == p2) continue;
A[p2] += ans;
// cout << ans << endl;
continue;
}
int r1 = A[p1-1] - A[p1] + 1 , r2 = A[p2+1] - A[p2] + 1;
if (r1 <= r2){
ans += r1;
A[p1] += r1;
A[p2] += r1;
p1++;
if (p1 == p2) continue;
A[p1] += ans;
}else{
ans += r2;
A[p2] += r2;
A[p1] += r2;
p2--;
if (p1 == p2) continue;
A[p2] += ans;
}
// cout << ans << endl;
}
cout << ans << endl;
}
signed main(){
// freopen("" , "r" , stdin);
// freopen("" , "w" , stdout);
// cout << setprecision(30);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int ts = 1;
// cin >> ts;
while(ts--){
solve();
}
}
