#include <bits/stdc++.h>
using namespace std;
#define forw(_,l,r) for(auto _=(l);_<(r);++_)
#define fors(_,r,l) for(auto _=(r);_>(l);--_)
#define RN return
#define MT make_tuple
#define fastio cin.tie(0),cout.tie(0),ios::sync_with_stdio(0);
void read(){}
template<typename T,typename...Types>
void read(T& x, Types&...args){
  x=0; char c=' '; bool sgn=0;
  while(isspace(c))c=getchar();
  if(c=='-')c=getchar(),sgn=1;
  while(isdigit(c))x=10*x+c-'0',c=getchar();
  if(sgn)x=-x;
  read(args...);
}

typedef vector<int> vi;
typedef long long ll;
const int NUM=250000*2+10;
const ll INFL=0x3f3f3f3f3f3f3f3f;
random_device rd;
mt19937 gen0(rd());
auto gen(){auto x=gen0();RN x<0?-x:x;}
struct tree{
  typedef int vec[NUM];
	typedef ll vecl[NUM];
	vecl data{},taga{},tagb{};
  vec siz{},rnd{},fa{},sn[2]{}; 
	int top=1,size=0;
  tree(){
    data[1]=INFL,siz[1]=1;tagb[1]=1;
  }
  inline int ssiz(int id,int opt){RN siz[sn[opt][id]];}
  inline int sid(int id){RN sn[1][fa[id]]==id;}
  void descend(int id){//id!=0
    ll t=taga[id];
		if(t){
			taga[id]=0;data[id]+=t;
			forw(i,0,2)taga[sn[i][id]]+=t;
		}t=tagb[id];
		if(t){
			tagb[id]=0;
			int lsiz=ssiz(id,0);
			tagb[sn[0][id]]+=t;
			data[id]+=t*lsiz;
			taga[sn[1][id]]+=t*lsiz+t;
			tagb[sn[1][id]]+=t;
		}
  }
  void sync(int id){
    siz[id]=siz[sn[0][id]]+siz[sn[1][id]]+1;
  }
  void rsync(int id){if(id)sync(id),rsync(fa[id]);}
  void rotate(int id){if(fa[id]&(-2)){
    int lt=sid(id),rt=lt^1;
    int nds[]={sn[lt][id],id,sn[rt][id],fa[id],sn[rt][fa[id]],fa[fa[id]]};
		for(int i:{3,1,4,0,2})descend(nds[i]);
    sn[sid(nds[3])][nds[5]]=nds[1];
    fa[nds[1]]=nds[5], sn[rt][nds[1]]=nds[3],
    fa[nds[3]]=nds[1], sn[lt][nds[3]]=nds[2];
    fa[nds[2]]=nds[3];
    sync(nds[3]); sync(id);
  }}
  void _ins(int rk,int d,int& id,int f){
    if(id==0){
      id=++top;
      tie(fa[id],rnd[id],siz[id],data[id])
      =MT(f     ,gen()  ,1      ,d       );
      rsync(f);
      for(int e=id;e;e=fa[e])if(rnd[e]<rnd[fa[e]])rotate(e);
    }else{
			descend(id);
      int lsiz=ssiz(id,0);
      if(rk<=lsiz)_ins(rk,d,sn[0][id],id);
      else _ins(rk-lsiz-1,d,sn[1][id],id);
    }
  }
  ll& _find_ele(int id,int rk){
		descend(id);
    int lsiz=ssiz(id,0),chd;
    if(rk<lsiz&&(chd=sn[0][id]))RN _find_ele(chd,rk);
    else if(rk>lsiz&&(chd=sn[1][id]))RN _find_ele(chd,rk-lsiz-1);
    else RN data[id];
  }
  void erase(int rk,char mode=0){
		if(mode==0){--size;}
    int id=mode?rk:&_find_ele(1,rk)-data;
    char opt=bool(sn[1][id])*2+bool(sn[0][id]);
    if(opt==3){
      int leaf=sn[0][id];
			while(descend(leaf),sn[1][leaf])leaf=sn[1][leaf];
      data[id]=data[leaf];rsync(id);erase(leaf,1); 
    }else{
      int son=0;if(opt)son=sn[opt-1][id],fa[son]=fa[id];
      sn[sid(id)][fa[id]]=son;rsync(fa[id]);
    }
  }
  void _inc(int id,int l,int r,ll a,ll b){
    descend(id);
		int lsiz=ssiz(id,0),chd,l2=l,r2=r;
		if(l==0&&r==siz[id]){taga[id]+=a,tagb[id]+=b;RN;}
		if(l<=lsiz&&r>lsiz)data[id]+=a+b*lsiz,r2=lsiz,l2=r2+1;
		if(l<=lsiz&&l!=r2&&(chd=sn[0][id]))_inc(chd,l,r2,a,b);
		if(r>lsiz&&l2!=r&&(chd=sn[1][id]))_inc(chd,l2-lsiz-1,r-lsiz-1,a+b*(lsiz+1),b);
  }
  void insert(int rk,int d){++size;int t=1;_ins(rk,d,t,0);}
	void inc(int k){RN _inc(1,0,size,0,k);}
  ll& operator[](int rk){RN _find_ele(1,rk);}
  void print(vi& v,int id=1){
		descend(id);
    int chd;
    if(chd=sn[0][id])print(v,chd);
		if(id!=1){v.push_back(data[id]);}
    if(chd=sn[1][id])print(v,chd);
  }
}tr;

int find_max_id(){
	int l=0,m1,m2,r=tr.size-1,d,t;ll mx=-INFL;
	for(;d=r-l,t=d/3,m1=l+t,m2=m1+t,d>=3;){
		ll y0=tr[l],y1=tr[m1],y2=tr[m2],y3=tr[r];
		if(y1<=y2)l=m1; if(y1>=y2)r=m2;
	}int id=l;
	forw(i,l,r+1)if(tr[i]>mx)mx=tr[i],id=i;
	RN id;
}

int main()
{
	tr.insert(0,0); int n; read(n);
	forw(i,0,n+1){
		int p=0;if(i<n)read(p);
		int id=find_max_id();ll x=tr[id];
		forw(_,0,2)tr.insert(id,x);
		tr.erase(0); tr.inc(p);
		// vi v;tr.print(v);
		// for(auto x:v)cout<<x<<' '; cout<<endl;
	}cout<<tr[0];
  RN 0;
}