#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long

const int N=1e6+5,Vmax=1e6;
const ll inf=1e18;
int n,a[N],lst=0;
ll f[N],ans,now;
vector<ll> V;
vector<int> pos[N];

struct BIT{
  ll tr[N],sum=0;
  int lowbit(int i){return i&(-i);}
  void upd(int x,ll v){sum+=v;for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=v;}
  ll qry(int x){
    ll res=0;
    for(int i=x;i>=1;i-=lowbit(i)) res+=tr[i];
    return res;
  }
}T[2];

ll s(int x){
  if(x<=0) return 0;
  return T[0].qry(x);
}

ll s(int l,int r){
  if(l<=r) return s(r)-s(l-1);
  return T[0].sum-s(l-1)+s(r);
}

bool in(int l,int r,int x){
  if(l<r) return l<=x&&x<=r;
//  cerr<<"in : " <<l<<' '<<r<<' '<<x<<endl;
  return !(r<x&&x<l);
}

ll c(int x){
  if(x<=0) return 0;
  return T[1].qry(x);
}

ll c(int l,int r){
  if(l<=r) return (c(r)-c(l-1))*now;
  return (T[1].sum-c(l-1)+c(r))*now;
}

void ckmn(ll &a,ll b){a=min(a,b);}

namespace SGT{
  #define mid ((l+r)>>1)
  #define lc p<<1
  #define rc p<<1|1
  #define lson l,mid,lc
  #define rson mid+1,r,rc
  
  struct sgt{
    ll v,hv,t,ht;
  }tr[N<<2];
  
  void pt(int p,ll hv,ll v){
    ckmn(tr[p].ht,tr[p].t+hv),tr[p].t+=v;
    ckmn(tr[p].hv,tr[p].v+hv),tr[p].v+=v;
  }
  
  void pd(int p){
    if(!tr[p].ht&&!tr[p].t) return;
    pt(lc,tr[p].ht,tr[p].t),pt(rc,tr[p].ht,tr[p].t);
    tr[p].t=tr[p].ht=0;
  }
  
  void upd(int l,int r,int p,int x,int y,ll v){
    if(x>y||x>r||y<l) return;
    if(x<=l&&y>=r) return pt(p,v,v);
    pd(p);
    if(x<=mid) upd(lson,x,y,v);
    if(y>mid) upd(rson,x,y,v);
  }
  
  void chg(int l,int r,int p,int x,ll v){
    if(x>r||x<l) return;
    if(l==r){
      tr[p].v=v,ckmn(tr[p].hv,v);
      return;
    }
    pd(p);
    x<=mid?chg(lson,x,v):chg(rson,x,v);
  }
  
  void build(int l,int r,int p){
    tr[p]={0,0,0,0};
    if(l==r){
      tr[p].hv=tr[p].v=inf;
      return;
    }
    build(lson),build(rson);
  }
  
  void sol(int l,int r,int p){
    if(l==r){
      V.pb(tr[p].hv);
      return;
    }
    pd(p);
    sol(lson),sol(rson);
  }
}

void solve(vector<int> &A,vector<int> &B){
  for(int i=0;i<(int)B.size();i++) T[0].upd(B[i],-a[B[i]]),T[1].upd(B[i],1);
  if(!(int)A.size()) A.pb(0);

  int len=(int)B.size(),it=0,cur=0;

  for(int j=0;j<len;j++) if(in(B[j],B[(j+1)%len],A[0])){it=j;break;}
  
  cur=it;
  for(int i=0;i<(int)A.size();i++){
    while(!in(B[it],B[(it+1)%len],A[i])) it=(it+1)%len;
    ckmn(f[B[it]],f[A[i]]+s(A[i],B[it]));
    ckmn(f[B[(it+1)%len]],f[A[i]]+s(B[(it+1)%len],A[i])+c(B[(it+1)%len],A[i]));
  }
  
  it=cur;
  SGT::build(0,len-1,1);
  for(int j=0;j<len;j++) if(j!=it) SGT::chg(0,len-1,1,j,f[A[0]]+s(A[0],B[j])+s(B[(j+1)%len],B[j])+c(B[(j+1)%len],A[0]));
  
  for(int i=1;i<(int)A.size();i++){
    int lst=it;
    while(!in(B[it],B[(it+1)%len],A[i])) it=(it+1)%len,SGT::chg(0,len-1,1,it,inf);
    
    ll dt=f[A[i]]-f[A[i-1]]-s(A[i-1],A[i]-1)+c(A[i-1]+1,A[i]);
  
    SGT::upd(0,len-1,1,0,min(lst,it)-1,dt);
    SGT::upd(0,len-1,1,max(lst,it)+1,len-1,dt);
    
    while(lst!=it){
      SGT::chg(0,len-1,1,lst,f[A[i]]+s(A[i],B[lst])+s(B[(lst+1)%len],B[lst])+c(B[(lst+1)%len],A[i]));
      lst=(lst+1)%len;
    }
  }
  V.clear(),SGT::sol(0,len-1,1);
  for(int j=0;j<len;j++) ckmn(f[B[(j+1)%len]],V[j]);
  
  it=cur;
  SGT::build(0,len-1,1);
  for(int j=0;j<len;j++) if(j!=it) SGT::chg(0,len-1,1,j,f[A[0]]+s(B[(j+1)%len],A[0])+s(B[(j+1)%len],B[j])+c(B[(j+1)%len],A[0]));
  
  for(int i=1;i<(int)A.size();i++){
    int lst=it;
    while(!in(B[it],B[(it+1)%len],A[i])) it=(it+1)%len,SGT::chg(0,len-1,1,it,inf);
    
    ll dt=f[A[i]]-f[A[i-1]]+s(A[i-1]+1,A[i])+c(A[i-1]+1,A[i]);
    
    SGT::upd(0,len-1,1,0,min(lst,it)-1,dt);
    SGT::upd(0,len-1,1,max(lst,it)+1,len-1,dt);
    
    while(lst!=it){
      SGT::chg(0,len-1,1,lst,f[A[i]]+s(B[(lst+1)%len],A[i])+s(B[(lst+1)%len],B[lst])+c(B[(lst+1)%len],A[i]));
      lst=(lst+1)%len;
    }    
  }
  V.clear(),SGT::sol(0,len-1,1);
  for(int j=0;j<len;j++) ckmn(f[B[j]],V[j]);

//  for(int i=0;i<(int)A.size();i++){
//    for(int j=0;j<len;j++){
//      if(in(B[j],B[(j+1)%len],A[i])){
//        ckmn(f[B[j]],f[A[i]]+s(A[i],B[j]));
//        ckmn(f[B[(j+1)%len]],f[A[i]]+s(B[(j+1)%len],A[i])+c(B[(j+1)%len],A[i]));
//        continue;
//      }
//      ckmn(f[B[(j+1)%len]],f[A[i]]+s(A[i],B[j])+s(B[(j+1)%len],B[j])+c(B[(j+1)%len],A[i]));
//      ckmn(f[B[j]],f[A[i]]+s(B[(j+1)%len],A[i])+s(B[(j+1)%len],B[j])+c(B[(j+1)%len],A[i]));
//    }
//  }
  
//  for(int i=0;i<len;i++) cerr<<"f( "<<B[i]<<" ) = "<<f[B[i]]<<endl;
  for(int i=0;i<len;i++) T[1].upd(B[i],-1);
}

int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n;
  for(int i=1;i<=n;i++) cin>>a[i],pos[a[i]].pb(i);
  for(int i=1;i<=n;i++) T[0].upd(i,a[i]),f[i]=inf;
  
  for(int i=Vmax;i>=1;i--) if((int)pos[i].size())
    now=i,solve(pos[lst],pos[i]),lst=i;
  ans=inf;
  for(auto i:pos[lst]) ckmn(ans,f[i]);
  cout<<ans;
  return 0;
}
/*
6
6 10 6 5 4 5

7
2 1 4 2 1 1 3 
*/