#include<bits/stdc++.h> using namespace std; #define ll long long #define int long long #define sht short #define pii pair<int,int> #define fr first #define sc second #define mk make_pair const int MAXN=70010,N=20,B=300,D=300; const ll inf=1e18; bool AAA; int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;} int n,m,a[MAXN],b[MAXN],bel[MAXN]; ll ans; struct segtree{ ll f[MAXN]; int lz[D+10],lz2[D+10]; void init(){ for(int i=1;i<=n;i++)f[i]=inf,bel[i]=(i-1)/B+1; } struct node{ int ls,rs,x; }t[MAXN*N]; #define lson (t[pos].ls) #define rson (t[pos].rs) int rt[D+10],cnt; ll qry(int x,ll y){ if(!x)return inf; return f[x]+y*x; } vector<int>rbs; int nnd(){ int res=0; if(rbs.empty())res=++cnt; else res=rbs.back(),rbs.pop_back(); return res; } void build(int &pos,int l,int r){ if(!pos)return; if(l==r){ t[pos].x=t[pos].ls=t[pos].rs=0; rbs.push_back(pos); return; } int mid=(l+r)>>1; build(lson,l,mid),build(rson,mid+1,r); t[pos].x=t[pos].ls=t[pos].rs=0; rbs.push_back(pos); pos=0; } void update(int &pos,int l,int r,int x){ if(!pos)pos=nnd(); if(!t[pos].x){t[pos].x=x;return;} int mid=(l+r)>>1; if(qry(x,mid)<qry(t[pos].x,mid))swap(t[pos].x,x); if(l==r)return; if(qry(x,l)<qry(t[pos].x,l))update(lson,l,mid,x); if(qry(x,r)<qry(t[pos].x,r))update(rson,mid+1,r,x); } ll query(int pos,int l,int r,int x){ if(!pos)return inf; if(l==r)return qry(t[pos].x,x); int mid=(l+r)>>1; if(x<=mid)return min(query(lson,l,mid,x),qry(t[pos].x,x)); else return min(query(rson,mid+1,r,x),qry(t[pos].x,x)); } void build(int x){if(!x)return; int l=(x-1)*B+1,r=min(n,x*B); build(rt[x],0,n); for(int i=l;i<=r;i++)update(rt[x],0,n,i); } int query(int l,int r){ ll res=inf; if(bel[l]==bel[r]){ for(int i=l;i<=r;i++)res=min(res,f[i]+lz[bel[l]]+lz2[bel[l]]*i); return res; } res=min(query(l,bel[l]*B),query(bel[r]*B-B+1,r)); for(int i=bel[l]+1;i<bel[r];i++)res=min(res,query(rt[i],0,n,lz2[i])+lz[i]); return res; } void update(int l,int r,int x){r=min(r,n);if(l>r)return; if(bel[l]==bel[r]){ for(int i=l;i<=r;i++)f[i]+=x; build(bel[l]); return; } update(l,bel[l]*B,x),update(bel[r]*B-B+1,r,x); for(int i=bel[l]+1;i<bel[r];i++)lz[i]+=x; } void update(int l,int r){r=min(r,n);if(l>r)return; if(bel[l]==bel[r]){ for(int i=l;i<=r;i++)f[i]+=i; build(bel[l]); return; } update(l,bel[l]*B),update(bel[r]*B-B+1,r); for(int i=bel[l]+1;i<bel[r];i++)lz2[i]++; } void upd(int x,ll y){ f[x]=min(f[x],y-lz[bel[x]]-lz2[bel[x]]*x); build(bel[x]); } }T; bool BBB; void slv(){ m=read(); int mx=0; for(int i=1;i<=m;i++){ int x=read(); if(x>=mx)ans+=x,mx=x; else a[++n]=x,b[n]=mx; } T.init(); for(int i=1;i<=n;i++){ ll tmp=T.query(0,a[i])+a[i]; T.update(0,a[i],b[i]); T.upd(a[i],tmp); T.update(a[i]+1,n); } printf("%lld",T.query(1,n)+ans); } signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); slv(); // cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"<<((&AAA)-(&BBB))/1024.0/1024<<"mb\n"; return 0; }