#include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define setIO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int) (x).size()
#define lc(i) 2*i
#define rc(i) 2*i+1
#define int long long
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vii = vector<ii>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vvb = vector<vb>;
const int N = 1e9 + 5, MOD = 1e9 + 7, INF = 1e17;
struct CHT {
struct Line {
int slope, yIntercept;
Line(int slope, int yIntercept) : slope(slope), yIntercept(yIntercept) {}
int val(int x) {
return slope * x + yIntercept;
}
int intersect(Line y) {
return (y.yIntercept - yIntercept + slope - y.slope - 1) / (slope - y.slope);
}
};
deque<pair<Line, int>> dq;
void insert(int slope, int yIntercept) {
Line newLine(slope, yIntercept);
while (sz(dq) > 1 && dq.back().second >= dq.back().first.intersect(newLine))
dq.pop_back();
if (dq.empty()) {
dq.emplace_back(newLine, 0);
return;
}
dq.emplace_back(newLine, dq.back().first.intersect(newLine));
}
int query(int x) {
while (sz(dq) > 1) {
if (dq[1].second <= x) dq.pop_front();
else break;
}
return dq[0].first.val(x);
}
int query2(int x) {
auto qry = *lower_bound(dq.rbegin(), dq.rend(),
make_pair(Line(0, 0), x),
[&](const pair<Line, int> &a, const pair<Line, int> &b) {
return a.second > b.second;
});
return qry.first.val(x);
}
};
signed main() {
FAST_IO;
#ifdef arujbansal_local
setIO("input.txt", "output.txt");
#endif
int n;
cin >> n;
int a[n + 1];
for (int i = 1; i <= n; i++) cin >> a[i];
CHT cht;
vi dp(n + 1);
dp[1] = a[1] * n;
cht.insert(n, 0);
int mx = a[1];
for (int i = 2; i <= n; i++) {
mx = max(mx, a[i]);
cht.insert(n - i + 1, dp[i - 1]);
dp[i] = cht.query(mx);
}
cout << dp[n];
}
