#include<bits/stdc++.h>
using namespace std;
const int NMAX = 200000+1;
#define int long long
const int INFINI = 1e17;
int N;
int hauteur[NMAX];
int chang[NMAX];
//int proGrand[2][NMAX]
/*
//lazy
int arbre[NMAX*3];
pair<int, int> debFin[NMAX*3];
int push[NMAX*3];
int construire(int noeud, int deb, int fin)
{
push[noeud] = 0;
debFin[noeud] = {deb, fin};
if(deb == fin-1)
{
return arbre[noeud] = chang[noeud];
}
int mil = deb+fin;
mil/=2;
return arbre[noeud] = min(construire(noeud*2, deb, mil), construire(noeud*2+1, mil, fin));
}
void pousser(int noeud)
{
int ajout = push[noeud];
push[noeud] = 0;
arbre[noeud] += ajout;
if(debFin[noeud].first != debFin[noeud].second-1)
{
push[noeud*2] += ajout;
push[noeud*2+1]+= ajout;
}
}
int trouverMin(int noeud, int deb, int fin)
{
pousser(noeud);
if((debFin[noeud].first <= deb)&&(debFin[noeud].second >= fin)) return arbre[noeud];
if((debFin[noeud].first >= fin) || (debFin[noeud].second <= deb)) return INFINI;
return min(trouverMin(noeud*2, deb, fin), trouverMin(noeud*2+1, deb, fin));
}
int maj(int noeud, int deb, int fin, int ajout)
{
pousser(noeud);
if((debFin[noeud].first <= deb)&&(debFin[noeud].second >= fin)){
push[noeud] += ajout;
pousser(noeud);
return arbre[noeud];
}
if((debFin[noeud].first >= fin) || (debFin[noeud].second <= deb)) return arbre[noeud];
return arbre[noeud] = min(maj(noeud*2, deb, fin, ajout), maj(noeud*2+1, deb, fin, ajout));
}/** */
//map<int, vector<int>> ordre;
void initChang()
{
int milieu = 1;
int hActu = -1;
if(milieu != 1)
{
for(int i = 1; i < milieu; i++)
{
chang[i] = max(hActu+1, hauteur[i]) - hauteur[i];
hActu = max(hActu+1, hauteur[i]);
}
}
hActu = -1;
if(milieu != N)
{
for(int i = N; i > milieu; i--)
{
chang[i] = max(hActu+1, hauteur[i]) - hauteur[i];
hActu = max(hActu+1, hauteur[i]);
}
}
if(milieu == 1)
{
chang[milieu] = max(hauteur[milieu], hauteur[milieu+1]+chang[milieu+1]+1) - hauteur[milieu];
}
else if(milieu == N)
{
chang[milieu] = max(hauteur[milieu], hauteur[milieu-1]+chang[milieu-1]+1) - hauteur[milieu];
}
else
{
chang[milieu] = max(hauteur[milieu], max(hauteur[milieu-1]+chang[milieu-1], hauteur[milieu+1]+chang[milieu+1])+1) - hauteur[milieu];
}
}
int resG[NMAX];
int resD[NMAX];
int augmentationG[NMAX+1];
int augmentationD[NMAX+1];
int ancAugG, ancAugD;
void initRes()
{
int milieu = 1;
for(int i = 1; i <= 1; i++)
{
resG[i] = resG[i-1];
if(chang[i] >= chang[i-1])
{
resG[i] += chang[i] - chang[i-1];
}
// augmentationG[i] = chang[i];
}
for(int i = N; i >= 1; i--)
{
resD[i] = resD[i+1];
if(chang[i] >= chang[i+1])
{
resD[i] += chang[i] - chang[i+1];
}
// augmentationD[i] = chang[i];
//cout << i << " " << resD << endl;
}
}
void updateChang(int iMilieuNouv)
{
if(iMilieuNouv == 2)
{
chang[iMilieuNouv-1] = 0;
}
else
chang[iMilieuNouv-1] = max(hauteur[iMilieuNouv-2]+chang[iMilieuNouv-2] +1, hauteur[iMilieuNouv-1]) - hauteur[iMilieuNouv-1];
if(iMilieuNouv == N)
{
chang[iMilieuNouv] = max(hauteur[iMilieuNouv], hauteur[iMilieuNouv-1]+chang[iMilieuNouv-1]+1) - hauteur[iMilieuNouv];
}
else
{
chang[iMilieuNouv] = max(hauteur[iMilieuNouv], max(hauteur[iMilieuNouv-1]+chang[iMilieuNouv-1], hauteur[iMilieuNouv+1]+chang[iMilieuNouv+1])+1) - hauteur[iMilieuNouv];
}
}
void updateRes(int imilieu)
{
//TO DO
if(imilieu > N) return;
if(imilieu == 2)
{
resG[1] = 0;
// augmentationG[1] = 0;
}
// for(int i = 1; i <= N; i++) cout << chang[i] << " ";
// cout << endl;
//augmentationG[imilieu-1] = chang[imilieu-1];
for(int i = max((long long)2, imilieu-1); i <= imilieu; i++)
{
resG[i] = resG[i-1];
if(chang[i] >= chang[i-1])
{
resG[i] += chang[i] - chang[i-1];
// cout << i << " " << resG[i] << ' ' << chang[i-1] << " " << chang[i] << endl;
}
// augmentationG[i] = chang[i];
}//*
if(imilieu == N) resD[N] = chang[N];
else
{
resD[imilieu] = resD[imilieu+1];
if(chang[imilieu] >= chang[imilieu+1])
{
resD[imilieu] += chang[imilieu] - chang[imilieu+1];
}
///cout << imilieu << " " << resD[imilieu+1] << " " << chang[imilieu] << " " << chang[imilieu+1] << endl;
}
// cout << "update " << imilieu << " resG : " << resG[imilieu] << " | rssD : " << resD[imilieu] <<endl;
}
int trouvercoutmin(int milieu)
{
//etape Montee
//construire(1, 0, N);
// cout << milieu << endl;
// for(int i = 0; i < N; i++) cout << chang[i] << " ";
// cout << endl;
//veritable
//*
// cout << milieu << " : " << resG << " " << resD << endl;
int a = max(resG[milieu], resD[milieu]);
//cout << milieu << " " << resG[milieu] << " " << resD[milieu] << endl;
updateChang(milieu+1);
updateRes(milieu+1);
return a;
/** */
/*
// cout << endl;
ordre.clear();
for(int i = 0; i < N; i++)
{
ordre[-chang[i]].push_back(i);
}
ordre[0].push_back({});
int derVal = -1;
set<pair<int, int>> intersG;
set<pair<int, int>> intersD;
int repG = 0, repD = 0;
for(auto a : ordre)
{
int val = -a.first;
auto ajouts = a.second;
if(derVal == -1) derVal = val;
int dif = derVal-val;
repG += dif * intersG.size();
repD += dif*intersD.size();
derVal = val;
// cout << val << endl;
for(int nouv : ajouts)
{
auto it = upper_bound(inters.begin(), inters.end(), pair<int, int>(nouv, nouv+1));
// cout << "jhl" << endl;
auto itAv = it;
// cout << "jhl" << endl;
// cout << "jhl" << endl;
auto itAp = it;
// cout << "jhl" << endl;
pair<int, int> nouvInter = {nouv, nouv+1};
// cout << "jhl" << endl;
if(itAv != inters.begin())
{
itAv--;
// cout << "jhl" << endl;
auto av = *itAv;
if(av.second == nouv)
{
nouvInter.first == av.first;
inters.erase(av);
}
}
if(itAp != inters.end())
{
auto ap = *itAp;
if(ap.first == nouv+1)
{
nouvInter.second == ap.second;
inters.erase(ap);
}
}
inters.insert(nouvInter);
}
}
return max(repG, repD);
/** */
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N;
for(int i = 1; i <= N; i++)
{
cin >> hauteur[i];
}
/*/
int deb = 0, fin = N, chang = 1;
for(int iD = 0; iD < 2; iD++)
{
stack<pair<int, int>> gros;
for(int i = deb; i != fin; i+= chang)
{
int elem = hauteur[i];
while((!gros.empty()) && (elem > gros.top().first)) gros.pop();
if(gros.empty())
{
proGrand[iD][i] = i;
}
else
proGrand[iD][i] = gros.top().second;
gros.push({elem, i});
}
deb= N-1;
fin = -1;
chang = -1;
}/** */
if(N == 1)
{
cout << 0;
return 0;
}
int meill = INFINI;
initChang();
initRes();
for(int iMil = 1; iMil <= N; iMil++)
{
int v = trouvercoutmin(iMil);
// cout << "rep " << v << endl;
meill = min(meill,v);
}
cout << meill;
}
