#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;
const int nmax = 10000001;
struct line{
ll k, b;
line(ll k, ll b) : k(k), b(b){
}
line(){
k = 0, b = 1e18;
}
ll get(ll x){
return k * x + b;
}
};
vector <line> t;
vector <int> le(nmax), ri(nmax);
void add(int v, int l, int r, line nw){
int m = (l + r) / 2;
if(l > r){
return;
}
bool left = t[v].get(l) < nw.get(l);
bool mid = t[v].get(m) < nw.get(m);
if(!mid) swap(t[v], nw);
if(mid == left){
if(ri[v] == 0){
ri[v] = t.size();
t.pb(nw);
return;
}
add(ri[v], m + 1, r, nw);
}
else{
if(le[v] == 0)
le[v] = t.size(), t.pb(nw);
else add(le[v], l, m, nw);
}
}
ll get(int v, int l, int r, ll pos){
if(l > r || v == 0) return 1e18;
ll m = (l + r) / 2;
if(pos > m)
return min(t[v].get(pos), get(ri[v], m + 1, r, pos));
return min(t[v].get(pos), get(le[v], l, m, pos));
}
line empt;
int32_t main(){
ios_base::sync_with_stdio(false); cin.tie(0);
t.pb(empt);
int n; cin >> n;
t.pb({n, 0});
vector <int> a(n + 1);
vector <int> b;
int mx = 0;
for(int i = 1; i <= n; ++i){
cin >> a[i];
if(a[i] > mx){
b.pb(i);
mx = a[i];
}
}
ll ans = 0;
for(int i= 0; i < b.size(); i++){
int x = b[i];
ll val = get(1, 1, 1e9, a[x]);
ans = val;
if(i != b.size() - 1){
int x = b[i + 1] - 1;
add(1, 1, 1e9, {n - x, ans});
}
}
cout << ans;
return 0;
}
