#include <bits/stdc++.h>
using namespace std;
const int lmt = 200005;
const long long MOD = 1000000007;
#define f first
#define S second
#define ll long long
#define ld long double
#define ull unsigned long long
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define for1(i, n) for(int i = 1; i < int(n); i++)
#define forv(i,a,n) for(int i = int(a); i < int(n); i++)
#define rof(i, n) for(int i = int(n); i >= 0; i--)
#define rofv(i,a,n) for(int i = int(n); i >= int(a); i--)
#define pb push_back
#define ins insert
#define pai pair<int, int>
#define pal pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define vld vector<long double>
/*
struct wer{
int a, b;
};
bool operator < (const wer &a, const wer &b){
return a.a < b.a;
}*/
ll dp[2][lmt];
ll ok[lmt];
ll OK[lmt];
ll D_[lmt];
ll D[lmt];
ll p[lmt];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n; cin>>n;
for(int i = 0; i < n; i++){
cin>>p[i];
}
if(n==2){
cout<<(p[0]==p[1] ? 1 : 0);
return 0;
}
int l = 1, r = n-2;
while(l<r){
while(l < r && p[l]>p[l-1]){
l++;
}
while(r>l && p[r]>p[r+1]){
r--;
}
if(r<=l || p[r]>p[r+1] || p[l]>p[l-1]){
break;
}
ll x = p[r+1] - p[r], y = p[l-1] - p[l];
if(x>y){
dp[1][r] = x-y;
}else{
dp[0][l] = y-x;
}
l++; r--;
}
for(int i = 1; i < n; i++){
dp[0][i] += dp[0][i-1];
}
for(int i = n-2; i >= 0; i--){
dp[1][i] += dp[1][i+1];
}
int L = p[0];
for(int i = 1; i < n-1; i++){
if(p[i]>p[i-1]){
if(p[i]<=L){
L++;
}else{
L = p[i];
}
D[i] = D[i-1];
}else{
L++;
D[i] = D[i-1] + (p[i-1] - p[i]) + 1;
}
ok[i]=L;
}
ll d = D[n-2];
if(ok[n-2]==p[n-1]){
d++;
}
L = p[n-1];
for(int i = n-2; i > 0; i--){
if(p[i]>p[i+1]){
if(p[i]<=L){
L++;
}else{
L = p[i];
}
D_[i] = D_[i+1];
}else{
L++;
D_[i] = D_[i+1] + (p[i+1] - p[i]) + 1;
}
OK[i]=L;
}
if(OK[1]==p[0]){
d = min(d, D_[1] + 1);
}else{
d = min(d, D_[1]);
}
for(int i = 1; i < n-2; i++){
if(p[i]==p[i+1]){
d = min(d, max(D[i] + dp[1][i+1], D_[i+1] + dp[0][i]) + 1);
}else{
d = min(d, max(D[i] + dp[1][i+1], D_[i+1] + dp[0][i]));
}
}
cout<<d;
return 0;
}
