#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;

#define ll long long
ll F[N],G[N],f[N],g[N],t[N];
vector<int>h[N<<1];
const int P=1e6+1;
const ll I=1e18;
void ad(ll &x,ll y){if(x>y)x=y;}
ll s[N],S;
void doi(int n,ll w){
    if(n==1){G[1]=F[1];return;}
    t[0]=0;
    for(int i=1;i<=n;i++)s[i]=s[i-1]+t[i-1],G[i]=I;
    t[0]=t[n],S=s[n]+t[n];
    ll p1=I,p2=I;
    for(int i=1;i<=n;i++){
        ad(G[i],p1+s[i]-t[i-1]*2+S+w*(n-i));
        ad(G[i],p2-s[i]+S*2-t[i]*2+w*(n-i-1));
        ad(p1,F[i]-s[i]+w*i),ad(p2,F[i]+s[i]+w*i);
        
    }
    p1=p2=I;
    for(int i=n;i;i--){
        ad(G[i],p1+S*2+s[i]-t[i-1]*2-w*i);
        ad(G[i],p2-s[i]-t[i]*2+S+w*(i-1));
        ad(p1,F[i]-s[i]+w*i);
        ad(p2,F[i]+s[i]+w*i);
    }
    /*for(int i=1;i<n;i++)for(int j=i+1;j<=n;j++)
    ad(G[j],F[i]+s[j]-s[i]-t[j-1]*2+w*(n-j+i)+S),
    ad(G[j],F[i]+S-s[j]+s[i]-t[j]*2+w*(n-j+i-1)+S),
    ad(G[i],F[j]+S-s[j]+s[i]-t[i-1]*2+w*(j-i)+S),
    ad(G[i],F[j]+s[j]-s[i]-t[i]*2+w*(j-i-1)+S);*/
}
#define pb push_back
ll tr[N];int n;
void ADD(int x,ll z){
    for(;x<=n;x+=(x&-x))tr[x]+=z;
}
ll ask(int x){
    ll s=0;
    for(;x;x-=(x&-x))s+=tr[x];
    return s;
}
ll ab(int l,int r){
    if(l<r)return ask(r)-ask(l);
    return ask(n)-(ask(l)-ask(r));
}
int a[N];
int main(){
    scanf("%d",&n);n++;
    a[1]=P;
    for(int i=2;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)ADD(i,a[i]),h[a[i]].pb(i);
    int w=0;
    for(int i=1;i<=n;i++)f[i]=g[i]=I;
    for(int i=P;i;i--)if(!h[i].empty()){
        for(int x:h[i])ADD(x,-i);
        if(!w){w=i,f[1]=g[1]=0;continue;}
        int sz=h[i].size();
        for(int x:h[w]){
            int o=lower_bound(h[i].begin(),h[i].end(),x)-h[i].begin();
            int q=(o<sz)?h[i][o]:h[i][0];
            ad(f[q],g[x]+ab(x,q));
            o--;
            q=(o>=0)?h[i][o]:h[i][sz-1];
            ad(f[q],g[x]+ab(q,x)+i);
        }
        for(int j=0;j<sz;j++)t[j+1]=ab(h[i][j],h[i][(j+1)%sz]),F[j+1]=f[h[i][j]];
        doi(sz,i);
        for(int j=0;j<sz;j++)g[h[i][j]]=G[j+1];
        w=i;
    }
    ll ans=I;
    for(int x:h[w])ad(ans,g[x]);
    printf("%lld",ans);
    return 0;
}