#include <bits/extc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(x) do{auto y = x; cout << #x << " = " << y << endl;}while(0)
// #define endl "\n"
#define unordered_map __gnu_pbds::gp_hash_table
using pii = pair<int, int>;
const int inf = 1ll << 60;
const int MOD = 1e9 + 7;
int n;
vector<int> t;
int eval(pii f, int x) {
if(x >= f.f) return inf;
return (n - x) * t[f.f - 1] + f.s;
}
struct lichao {
int tl, tr;
pii f;
lichao *lc, *rc;
void insert(pii f2) {
int tm = (tl + tr) / 2;
if(eval(f2, tm) < eval(f, tm)) swap(f, f2);
if(tl + 1 == tr) return;
if(eval(f2, tl) <= eval(f, tl)) {
if(!lc) {
lc = new lichao{tl, tm, f2};
} else {
lc->insert(f2);
}
} else if(eval(f2, tr - 1) <= eval(f, tr - 1)) {
if(!rc) {
rc = new lichao{tm, tr, f2};
} else {
rc->insert(f2);
}
}
}
int query(int x) {
int tm = (tl + tr) / 2;
int res = eval(f, x);
if(x < tm && lc) return min(res, lc->query(x));
if(x >= tm && rc) return min(res, rc->query(x));
return res;
}
};
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
t.resize(n);
for(int i = 0; i < n; i++) {
cin >> t[i];
}
for(int i = 1; i < n; i++) {
t[i] = max(t[i], t[i - 1]);
}
vector<int> dp(n);
lichao lct{0, n, {n, 0}};
for(int i = n - 1; i >= 0; i--) {
dp[i] = lct.query(i);
lct.insert({i, dp[i]});
}
cout << dp[0] << endl;
}
