#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
struct Lichao_Tree {
static const int L = 0, R = 1e6;
struct line {
long long a, b;
line() {}
line(const long long& _a, const long long& _b) : a(_a), b(_b) {}
long long operator () (const long long& x) {return a * x + b;}
};
struct tree_node {
tree_node *left = nullptr, *right = nullptr;
line d = line(0, -inf);
void insert(int l, int r, line nd) {
int mid = (l + r) / 2;
bool optl = d(l) < nd(l), optm = d(mid) < nd(mid), optr = d(r) < nd(r);
if (optm) swap(d, nd);
if (l == r) return;
if (optl != optm) {
if (!left) left = new tree_node;
(*left).insert(l, mid, nd);
}
if (optr != optm) {
if (!right) right = new tree_node;
(*right).insert(mid + 1, r, nd);
}
}
long long query(int l, int r, int x) {
long long res = d(x);
int mid = (l + r) / 2;
if (left && x < mid) res = max(res, (*left).query(l, mid, x));
if (right && x > mid) res = max(res, (*right).query(mid + 1, r, x));
return res;
}
} root;
void insert(const long long& a, const long long& b) {root.insert(L, R, line(-a, -b));}
long long query(int x) {return -root.query(L, R, x);}
} tree;
int t[1000008];
long long dp[1000008];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> t[i];
t[i] = max(t[i], t[i - 1]);
}
reverse(t + 1, t + n + 1);
for (int i = 1; i <= n; ++i) {
tree.insert(t[i], dp[i - 1]);
dp[i] = tree.query(i);
// cout << dp[i] << ' ';
}
// cout << endl;
cout << dp[n];
}
