#include <bits/stdc++.h>
#define x first
#define X first
#define y second
#define Y second
#define pb push_back
#define PB push_back
#define all(a) begin(a),end(a)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;

const int N = 5e5 + 500,M=1<<19;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const char en='\n';
const ll LLINF=1ll<<60;

ll seg[M*2+10],h[N],ovas[N];

void upd(int i,ll x)
{
	seg[i+=M]=x;
	for (i/=2;i;i/=2) seg[i]=seg[i*2]+seg[i*2+1];
}

ll ge(int l,int r,int lo=0,int hi=M,int i=1)
{
	if (lo>=l && hi<=r) return seg[i];
	if (lo>=r || hi<=l) return 0;
	int mid=(lo+hi)/2;
	return ge(l,r,lo,mid,i*2)+ge(l,r,mid,hi,i*2+1);
}

ll pr(int i)
{
	return ge(0,i);
}

int n;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	map<ll,vi> po;
	for (int i=0;i<n;++i) cin>>h[i],po[-h[i]].pb(i),upd(i,h[i]);
	set<pair<ll,int>> posi;
	posi.insert({0ll,0});
	set<int> sl;
	for (int i=0;i<n;++i) sl.insert(i);
	for (auto me: po)
	{
		ll va=-me.x;
		vi gd=me.y;
		vl befs(gd.size(),LLINF);
		set<pair<ll,int>> nov;
		vi opos;
		for (auto x: posi) opos.pb(x.y),ovas[x.y]=x.x;
		sort(all(opos));
		for (auto x: opos) nov.insert({ovas[x]+pr(x),x});
		int ci=0;
		int gs=gd.size(),os=opos.size();
		ll sve1=pr(n);
		ll sve2=pr(n)-gs*va;
		for (int i=0;i<gs;++i)
		{
			//10 after c
			while (ci<os && opos[ci]<gd[i])
			{
				int cu=opos[ci];
				auto it=nov.find({ovas[cu]+pr(cu),cu});
				pair<ll,int> nn={ovas[cu]+pr(cu)+pr(n),cu};
				nov.erase(it);
				nov.insert(nn);
				++ci;
			}
			ll csve=sve2;
			if (i==0) csve-=pr(gd[i])+pr(n)-pr(gd.back()+1);
			else csve-=pr(gd[i])-pr(gd[i-1]+1);
			befs[(i+gs-1)%gs]=min(befs[(i+gs-1)%gs],nov.begin()->x-pr(gd[i])+csve);
		}
		
		//cout<<"after left p2"<<endl;
		//for (int i=0;i<gs;++i) cout<<gd[i]<<' '<<befs[i]<<en;
		
		for (auto x: gd) upd(x,0);
		nov.clear();
		for (auto x: opos)
		{
			//cout<<"st"<<x<<' '<<ovas[x]<<' '<<pr(x)<<en;
			nov.insert({ovas[x]-pr(x),x});
		}
		ci=os-1;
		for (int i=gs-1;i>=0;--i)
		{
			//10 after c
			while (ci>=0 && opos[ci]>gd[i])
			{
				int cu=opos[ci];
				//cout<<"changing "<<cu<<" from "<<ovas[cu]-pr(cu)<<" to "<<ovas[cu]-pr(cu)+pr(n)<<endl;
				auto it=nov.find({ovas[cu]-pr(cu),cu});
				pair<ll,int> nn={ovas[cu]-pr(cu)+pr(n),cu};
				nov.erase(it);
				nov.insert(nn);
				--ci;
			}
			ll csve=sve2;
			if (i==0) csve-=pr(gd[i])+pr(n)-pr(gd.back()+1);
			else csve-=pr(gd[i])-pr(gd[i-1]+1);
			//cout<<i<<' '<<nov.begin()->x<<' '<<nov.begin()->y<<' '<<pr(gd[i])<<' '<<csve<<en;
			befs[(i+gs-1)%gs]=min(befs[(i+gs-1)%gs],nov.begin()->x+pr(gd[i])+csve);
		}
		
		//cout<<"after left p1"<<endl;
		//for (int i=0;i<gs;++i) cout<<gd[i]<<' '<<befs[i]<<en;
		
		nov.clear();
		for (auto x: opos) nov.insert({ovas[x]+pr(x+1),x});
		ci=0;
		for (int i=0;i<gs;++i)
		{
			//10 before c
			while (ci<os && opos[ci]<gd[i])
			{
				int cu=opos[ci];
				auto it=nov.find({ovas[cu]+pr(cu+1),cu});
				pair<ll,int> nn={ovas[cu]+pr(cu+1)+pr(n),cu};
				nov.erase(it);
				nov.insert(nn);
				++ci;
			}
			ll csve=sve1;
			if (i==gs-1) csve-=pr(gd[0])+pr(n)-pr(gd[i]+1);
			else csve-=pr(gd[i+1])-pr(gd[i]+1);
			befs[i]=min(befs[i],nov.begin()->x-pr(gd[i])+csve);
		}
		
		//cout<<"after right p1"<<endl;
		//for (int i=0;i<gs;++i) cout<<gd[i]<<' '<<befs[i]<<en;
		
		//transform 10 into -10
		
		nov.clear();
		for (auto x: gd) upd(x,-va);
		//cout<<"pr: "<<endl;
		//for (int i=0;i<=n;++i) cout<<pr(i)<<' ';
		//cout<<en;
		for (auto x: opos) nov.insert({ovas[x]-pr(x),x});
		ci=os-1;
		for (int i=gs-1;i>=0;--i)
		{
			while (ci>=0 && opos[ci]>gd[i])
			{
				int cu=opos[ci];
				auto it=nov.find({ovas[cu]-pr(cu),cu});
				pair<ll,int> nn={ovas[cu]-pr(cu)+pr(n),cu};
				nov.erase(it);
				nov.insert(nn);
				--ci;
			}
			ll csve=sve1;
			if (i==gs-1) csve-=pr(gd[0])+pr(n)-pr(gd[i]+1);
			else csve-=pr(gd[i+1])-pr(gd[i]+1);
			//cout<<i<<' '<<nov.begin()->x<<' '<<nov.begin()->y<<' '<<pr(gd[i]+1)<<' '<<csve<<en;
			befs[i]=min(befs[i],nov.begin()->x+pr(gd[i]+1)+csve);
		}
		posi.clear();
		for (auto x: gd) sl.erase(x);
		if (sl.empty())
		{
			ll mi=LLINF;
			for (int i=0;i<gs;++i) mi=min(mi,befs[i]);
			cout<<mi<<en;
			exit(0);
		}
		map<int,ll> mav;
		for (int i=0;i<gs;++i)
		{
			auto it=sl.lower_bound(gd[i]);
			if (it==sl.end()) it=sl.begin();
			if (mav.find(*it)==mav.end()) mav[*it]=befs[i];
			else mav[*it]=min(mav[*it],befs[i]);
		}
		for (auto x: mav) posi.insert({x.y,x.x});
		for (auto x: gd) upd(x,0);
		//cout<<"after right p2"<<endl;
		//for (int i=0;i<gs;++i) cout<<gd[i]<<' '<<befs[i]<<en;
		//for (auto x: posi) cout<<x.x<<' '<<x.y<<en;
		//cout<<endl;
	}
}