#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
using vi = vector<int>;
using vl = vector<long long>;
using vpi = vector<pair<int, int>>;
using vpl = vector<pair<long long, long long>>;
#define fur(i, a, b) for(ll i = a; i <= (ll)b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll)b; --i)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define nl "\n"
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const ll inf = 1e16L;
struct CHT {
struct Line {
ll m, c;
Line(ll a, ll b){
m = a;
c = b;
}
ll isect(Line &other) {
return (c - other.c + other.m - m + 1) / (other.m - m);
}
ll val(ll x) {
return m*x + c;
}
};
deque<pair<Line, ll>> dq;
void insert(ll m, ll c) {
Line nex(m, c);
if(dq.empty()) {
dq.eb(nex, 0);
return;
}
while(!dq.empty()) {
Line pr = dq.back().fr;
ll x = dq.back().sc;
if(nex.m == pr.m) {
if(nex.c > pr.c) {
return;
}
} else if(nex.isect(pr) > x) {
break;
}
dq.pop_back();
}
if(dq.empty()) {
dq.eb(nex, 0);
return;
}
dq.eb(nex, nex.isect(dq.back().fr));
}
ll query(ll x) {
ll m = dq.size();
while(m > 1 && dq[1].sc <= x) {
dq.pop_front();
--m;
}
return dq.front().fr.val(x);
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
ll n;
cin >> n;
ll t[n + 1];
fur(i, 1, n)
cin >> t[i];
ll dp[n + 1];
dp[0] = 0;
ll p[n + 1];
p[1] = 1;
fur(i, 2, n) {
if(t[i] > t[p[i - 1]])
p[i] = i;
else p[i] = p[i - 1];
}
CHT cht;
fur(i, 1, n) {
cht.insert(n - i + 1, dp[i - 1]);
dp[i] = cht.query(t[p[i]]);
}
cout << dp[n] << nl;
}
