#include<bits/stdc++.h>
using namespace std;
const int NMAX = 200000;
#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 = 0;
int hActu = -1;
if(milieu != 0)
{
for(int i = 0; i < milieu; i++)
{
chang[i] = max(hActu+1, hauteur[i]) - hauteur[i];
hActu = max(hActu+1, hauteur[i]);
}
}
hActu = -1;
if(milieu != N-1)
{
for(int i = N-1; i > milieu; i--)
{
chang[i] = max(hActu+1, hauteur[i]) - hauteur[i];
hActu = max(hActu+1, hauteur[i]);
}
}
if(milieu == 0)
{
chang[milieu] = max(hauteur[milieu], hauteur[milieu+1]+chang[milieu+1]+1) - hauteur[milieu];
}
else if(milieu == N-1)
{
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];
}
}
void updateChang(int iMilieuNouv)
{
if(iMilieuNouv == 1)
{
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-1)
{
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];
}
}
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
//*
int resG = 0;
int augmentationG = 0;
for(int i = 0; i <= milieu; i++)
{
if(chang[i] >= augmentationG)
{
resG += chang[i] - augmentationG;
augmentationG += chang[i] - augmentationG;
}
else
{
augmentationG = chang[i];
}
}
int resD = 0, augmentationD = 0;
for(int i = N-1; i >= milieu; i--)
{
if(chang[i] >= augmentationD)
{
resD += chang[i] - augmentationD;
augmentationD += chang[i] - augmentationD;
}
else
{
augmentationD = chang[i];
}
//cout << i << " " << resD << endl;
}
// cout << milieu << " : " << resG << " " << resD << endl;
updateChang(milieu+1);
return max(resG, resD);
/** */
/*
// 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 = 0; 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();
for(int iMil = 0; iMil < N; iMil++)
{
int v = trouvercoutmin(iMil);
// cout << "rep " << v << endl;
meill = min(meill,v);
}
cout << meill;
}
