#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
struct ConvexHull {
deque<pair<ll,ll> > dq;
ll f(pair<ll,ll> line,ll x){
return line.first * x + line.second;
}
ll query(ll x){
while(dq.size() > 1){
if(f(dq[0],x) < f(dq[1],x)){
dq.pop_front();
}else{
break;
}
}
return f(dq[0],x);
}
long double Intersect(ll a,ll b,ll c,ll d){
return (long double)(d - b) / (a - c);
}
long double intersect(pair<ll,ll> p1,pair<ll,ll> p2){
return Intersect(p1.first,p1.second,p2.first,p2.second);
}
void ins(ll m,ll c){
pair<ll,ll> line = make_pair(m,c);
while(dq.size() > 1){
ll s = dq.size();
if(intersect(dq[s - 1],line) <= intersect(dq[s - 2],line)){
dq.pop_back();
}else{
break;
}
}
dq.push_back(line);
}
} CH; //returns maximum y
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
ll N;
cin>>N;
ll T[N + 1];
for(ll i = 1;i <= N;i++){
cin>>T[i];
}
T[0] = 0;
ll premaxT[N + 1];
premaxT[0] = 0;
for(ll i = 1;i <= N;i++){
premaxT[i] = max(premaxT[i - 1],T[i]);
}
ll dp[N + 1];
dp[0] = 0;
CH.dq.clear();
CH.ins(-N,0);
for(ll i = 1;i <= N;i++){
if(premaxT[i - 1] < T[i]){
dp[i] = -CH.query(T[i]);
ll ptr = i;
while(ptr < N && T[ptr] <= T[i]){
ptr++;
}
CH.ins(ptr - N - 1,-dp[i]);
}else{
dp[i] = dp[i - 1];
}
}
cout<<dp[N]<<'\n';
}
