#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e?x++:x--))
#define sz(x) (int) (x).size()
#define all(x) (x).begin(),(x).end()
struct line{
ll m,c;
line (ll _m,ll _c){
m=_m,c=_c;
}
ll get(ll x){
return m*x+c;
}
};
struct LCH{
deque<line> dq;
double POI(line i,line j){
return (double)(i.c-j.c)/(double)(j.m-i.m);
}
void insert(line i){
//cout<<"debug: "<<i.m<<" "<<i.c<<endl;
while (sz(dq)>=2 && POI(dq.back(),i)<POI(dq[sz(dq)-2],dq.back())) dq.pop_back();
dq.push_back(i);
//for (auto &it:dq) cout<<it.m<<"_"<<it.c<<" ";cout<<endl;
}
ll query(ll x){
while (sz(dq)>=2 && POI(dq[0],dq[1])<x) dq.pop_front();
return dq.front().get(x);
}
} hull=LCH();
int n;
ll arr[1000005];
vector<ii> v;
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin>>n;
rep(x,0,n){
cin>>arr[x];
if (v.empty() || v.back().fi<arr[x]){
v.push_back(ii(arr[x],1));
}
else{
v.back().se++;
}
}
ll pw=0;
//for (auto &it:v) cout<<it.fi<<" "<<it.se<<endl;
for (auto &it:v) pw+=it.se;
hull.insert(line(pw,0));
ll ans=0;
for (auto &it:v){
ans=hull.query(it.fi);
//cout<<ans<<endl;
pw-=it.se;
hull.insert(line(pw,ans));
}
cout<<ans<<endl;
}
