#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 2*(1e6)+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e17 + 77;
#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>
ll n, m, k;
ll a[dim], dp[dim];
deque<pll> dq;
ld cross(pll p1, pll p2){
return (ld)((p1.se-p2.se)/(ld)(p2.fi-p1.fi));
}
void add(pll cur){
while(dq.size()>=2 && cross(dq[dq.size()-2], cur)>=cross(dq[dq.size()-1], cur)){
dq.pop_back();
}
dq.push_back(cur);
}
ll get(ll x){
while(dq.size()>1 && cross(dq[1], dq[0])<x)dq.pop_front();
pll cur=dq.front();
return cur.fi*x+cur.se;
}
int main() {
ll u, w,q, v, y;
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1; i<=n; i++){
cin>>a[i];
}
ll mx=0;
map<ll, ll> mp;
for(int i=1; i<=n; i++){
mx=max(mx, a[i]);
a[i]=mx;
mp[a[i]]++;
}
vector<pll> g;
for(auto x: mp){
g.pb(x);
}
m=g.size();
ll len=n;
add({n, 0});
for(int i=0; i<m; i++){
dp[i]=get(g[i].fi);
len-=g[i].se;
add({len, dp[i]});
}
cout<<dp[m-1]<<endl;
return 0;
}
