#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]; }