#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> piii;
const ll NMAX = 1000001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 101;
const ll nr_of_bits = 35;
struct functie{
ll a, b;
ll valoare(ll x){
return a * x + b;
}
};
functie tree[NMAX * 4];
void update(ll node, ll st, ll dr, functie x){
if(st == dr){
if(x.valoare(st) < tree[node].valoare(st)){
swap(x, tree[node]);
}
return;
}
ll mid = (st + dr) / 2;
ll xs = x.valoare(st);
ll xm = x.valoare(mid);
ll ts = tree[node].valoare(st);
ll tm = tree[node].valoare(mid);
if(xm < tm){
if(xs < ts){
swap(tree[node], x);
update(node * 2 + 1, mid + 1, dr, x);
}else{
swap(tree[node], x);
update(node * 2, st, mid, x);
}
}else{
if(xs < ts){
update(node * 2, st, mid, x);
}else{
update(node * 2 + 1, mid + 1, dr, x);
}
}
}
ll query(ll node, ll st, ll dr, ll col){
if(st == dr){
return tree[node].valoare(col);
}
ll mid = (st + dr) / 2;
ll val = tree[node].valoare(col);
if(col <= mid){
return min(query(node * 2, st, mid, col), val);
}else{
return min(val, query(node * 2 + 1, mid + 1, dr, col));
}
}
vector <pii> grupe;
ll dp[NMAX + 1];
ll v[NMAX];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
for(ll i = 0; i < 4 * NMAX; i++){
tree[i].b = INF;
}
ll n, i, ind = 1;
cin >> n;
cin >> v[1];
for(i = 2; i <= n; i++){
cin >> v[i];
if(v[i] > v[ind]){
grupe.push_back({v[ind], ind});
ind = i;
}
}
grupe.push_back({v[ind], ind});
dp[grupe.size() + 1] = 0;
n++;
for(i = grupe.size() ; i >= 1; i--){
update(1, 1, n, {grupe[i - 1].first, dp[i + 1]});
dp[i] = query(1, 1, n, (n - grupe[i - 1].second + 1 - 1));
}
cout << dp[1];
return 0;
}
