#include<bits/stdc++.h> using namespace std; using ll=long long; const int N=1e5+10,B=300; int n,a[N]; ll f[N];int mx[N]; int bel[N],L[N],R[N]; vector<int> hull[N];int it[N]; ll tg1[N],tg2[N]; void down(int id){ for(int i=L[id];i<=R[id];i++){ f[i]+=tg1[id]+i*tg2[id]; }tg1[id]=0;tg2[id]=0; } void updit(int id){ while(it[id]){ int x=hull[id][it[id]],y=hull[id][it[id]-1]; if(f[x]+tg2[id]*x>=f[y]+tg2[id]*y){ it[id]--; }else{ break; } } } void init(int id){ hull[id].clear(); for(int i=L[id];i<=R[id];i++){ while(hull[id].size()>=2){ int y=hull[id].back();hull[id].pop_back(); int x=hull[id].back(); if((f[y]-f[x])*(i-y)<(f[i]-f[y])*(y-x)){ hull[id].push_back(y);break; } }hull[id].push_back(i); }it[id]=hull[id].size()-1; } ll qmn(int id){ updit(id);int x=hull[id][it[id]]; return tg1[id]+f[x]+tg2[id]*x; } int main(){ //freopen("separate.in","r",stdin); //freopen("separate.out","w",stdout); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=0;i<=n;i++) bel[i]=i/B+1;bel[n+1]=bel[n]+1; for(int i=1;i<=bel[n];i++) L[i]=(i-1)*B,R[i]=min(i*B-1,n); for(int i=0;i<=n;i++) f[i]=1e12;f[0]=0; for(int i=1;i<=bel[n];i++) init(i); for(int i=1;i<=n;i++){ if(a[i]>mx[i-1]){ mx[i]=a[i]; ll mn=1e18; for(int j=1;j<=bel[n];j++) mn=min(mn,qmn(j)),tg1[j]+=a[i]; int bl=bel[mx[i-1]]; down(bl);f[mx[i-1]]=min(f[mx[i-1]],mn+a[i]); init(bl); }else{ mx[i]=mx[i-1]; ll mn=1e18; int bl=bel[a[i]]; for(int j=1;j<bl;j++) mn=min(mn,qmn(j)),tg1[j]+=mx[i-1]; down(bl); for(int j=L[bl];j<=a[i];j++) mn=min(mn,f[j]),f[j]+=mx[i-1]; f[a[i]]=min(f[a[i]],mn+a[i]); init(bl); bl=bel[a[i]+1];down(bl); for(int j=a[i]+1;j<=R[bl];j++) f[j]+=j;init(bl); for(int j=bl+1;j<=bel[n];j++) tg2[j]++; } } ll ans=1e18; for(int i=1;i<=bel[n];i++) down(i); for(int i=0;i<=n;i++) ans=min(ans,f[i]); cout<<ans<<endl; return 0; }