#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const ll inf=1e18;
const int N=1e6+10;
int n,a[N],b[N];
vi t[N];
ll f1[N],f[N],f2[N];
void gmin(ll &a,ll b){a=min(a,b);}
struct{
	ll t[N],s;
	void add(int x,int a){for(;x<=n;t[x]+=a,x+=x&(-x));}
	ll sum(int x){for(s=0;x;s+=t[x],x-=x&(-x));return s;}
}t1,t2;
ll go1(int x,int y)//x->y  x->n 1->y
{
	if(x<=y) return t1.sum(y-1)-t1.sum(x-1);
	else return go1(x,n+1)+go1(1,y);
//	if(x<y) return go1(x,0)+go1(n,y);
//	else return bit::sum(x)-bit::sum(y);
}
ll go2(int x,int y)//y<-x
{
	if(x>=y) return t2.sum(x-1)-t2.sum(y-1);
	else return go2(x,1)+go2(n+1,y);
//	if(x>y) return go2(x,n)+go2(0,y);
//	else return bit::sum(y)-bit::sum(x);
}
ll go(int x,int y){return min(go1(x,y),go2(x,y));}
ll calc(int x,int y){return f[x]+go1(x,y);}
void trans1(vi a,int val)//right-left
{
	int m=a.size();
	for(int i:a) t1.add(i,-val),f1[i]=f[i];
	for(int i=1,j=0;i<m;i++)
	{
		if(f[a[i]]>calc(a[j],a[i]))
			f1[a[i]]=calc(a[j],a[i]);
		else j=i;
	}
	for(int i=m-2,j=m-1;i>=0;i--)
	{
		if(calc(a[j],a[i])>calc(a[i+1],a[i])) j=i+1;
		gmin(f1[a[i]],calc(a[j],a[i]));
	}
	for(int i=0;i<m;i++)
	{
		int x=a[(i+1)%m];
		f2[x]=f1[a[i]]+go2(a[i],x);
	}
	for(int i:a) t1.add(i,val);
}
void trans2(vi a)//left-right
{
	int m=a.size();
	for(int i:a) f1[i]=f[i];
	for(int c=0;c<2;c++)
		for(int i=m-1;i>=0;i--)
		{
			int x=a[(i-1+m)%m];
			gmin(f1[x],f1[a[i]]+go2(a[i],x));
		}
	for(int i=0;i<m;i++)
	{
		int x=a[(i+1)%m];
		f[a[i]]=f1[x]+go1(x,a[i]);
	}
}
void trans3(vi a,vi b)
{
	for(int x:b) f[x]=inf;
	int n1=a.size(),n2=b.size();
	for(int x:b)
		gmin(f[x],f[a[0]]+go(a[0],x)),
		gmin(f[x],f[a.back()]+go(a.back(),x));
	vector<pair<int,int>> v;
	for(auto x:a) v.push_back({x,1});
	for(int x:b) v.push_back({x,2});
	sort(v.begin(),v.end());
	for(int i=0,lst=-1;i<n1+n2;i++)
	{
		if(v[i].second==1) lst=v[i].first;
		else if(lst!=-1) gmin(f[v[i].first],f[lst]+go1(lst,v[i].first));
	}
	reverse(v.begin(),v.end());
	for(int i=0,lst=-1;i<n1+n2;i++)
	{
		if(v[i].second==1) lst=v[i].first;
		else if(lst!=-1) gmin(f[v[i].first],f[lst]+go2(lst,v[i].first));
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
	sort(b+1,b+n+1);
	int m=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(b+1,b+m+1,a[i])-b,t[a[i]].push_back(i);
	for(int i=1;i<=n;i++) t1.add(i,b[a[i]]),t2.add(i,b[a[i]]);
	for(int i=m;i;i--)
	{
		for(int j:t[i]) t1.add(j,-b[a[j]]);
		if(i<m) trans3(t[i+1],t[i]);
		else for(int y:t[i]) f[y]=go(1,y);
		trans1(t[i],i);
		trans2(t[i]);
		for(int j:t[i]) gmin(f[j],f2[j]);
		for(int j:t[i]) t2.add(j,-b[a[j]]);
	}
	ll ans=1e18;
	for(auto x:t[1]) ans=min(ans,f[x]);
//	for(int i=1;i<=n;i++) printf("%lld\n",f[i]);
	printf("%lld\n",ans);
}