#include <bits/stdc++.h> using namespace std; #define endl '\n' #define dl double #define int long long #define ul uint_fast32_t #define ll int_fast64_t #define dll long double #define ull uint_fast64_t #define spektar this_thread::sleep_for(chrono::milliseconds(50)) void solve(){ int n; cin >> n; vector<ll> k(n); for(auto& i:k) cin >> i; vector<ll> k1=k,k2=k; vector<ll> kk1(n); vector<ll> kk2(n); kk1[0]=0; kk2[n-1]=0; ll max1=0; for(int i=1; i<n; i++){ ll s1=max(k1[i],k1[i-1]+1)-k1[i]; k1[i]=max(k1[i],k1[i-1]+1); kk1[i]=s1; } for(int i=n-2; i>=0; i--){ ll s1=max(k2[i],k2[i+1]+1)-k2[i]; k2[i]=max(k2[i],k2[i+1]+1); kk2[i]=s1; } vector<ll> pref1(n+1),pref2(n+1); pref1[0]=0; pref2[n]=0; for(int i=0; i<n; i++){ pref1[i+1]=pref1[i]+kk1[i]; } for(int i=n-1; i>=0; i--){ pref2[i]=pref2[i+1]+kk2[i]; } ll min1=1000000000000000000; for(int i=0; i<n; i++){ min1=min(min1,min(max(max(kk1[i],kk2[i]),pref1[i])+pref2[i+1],max(pref2[i+1],max(kk1[i],kk2[i]))+pref1[i])); } cout << min1 << endl; } signed main(){ //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t=1; //cin >> t; while(t--){ solve(); } }