#include <bits/stdc++.h> using namespace std; #define int long long #define rep(x, a, b) for(auto x=a;(a<b?x<b:x>b);(a<b?x++:x--)) #define all(a) a.begin(), a.end() #define srtvc(a) sort(all(a)) #define bcsrtvc(a) sort(all(a), greater<__typeof__(a[0])>()) #define ppf pop_front #define ppb pop_back #define pf push_front #define pb push_back #define ef emplace_front #define eb emplace_back #define fr first #define sc second #define pq priority_queue #define pii pair<int, int> #define vc vector #define dq deque #define sz(a) a.size() #define mnto(x,y) x = min(x, (__typeof__(x))y) #define mxto(x,y) x = max(x, (__typeof__(x))y) #define setval(arr, x) memset(arr, x, sizeof(arr)) template<typename T> using vv = vc<vc<T>>; struct Line { __int128 m, c; Line(__int128 _m, __int128 _c) : m(_m), c(_c) {} __int128 eval(__int128 x) const { return m * x + c; } }; struct CHT { vc<Line> hull; bool bad(const Line &L1, const Line &L2, const Line &L3) { __int128 left = (L2.c - L1.c) * (L1.m - L3.m); __int128 right = (L3.c - L1.c) * (L1.m - L2.m); return left <= right; } void add(__int128 m, __int128 c) { Line L(m, c); while (sz(hull) >= 2 && bad(hull[sz(hull)-2], hull.back(), L)) hull.ppb(); hull.pb(L); } __int128 query(__int128 x) { int l = 0, r = sz(hull) - 1; while (l < r) { int mid = (l + r) >> 1; if (hull[mid].eval(x) <= hull[mid+1].eval(x)) r = mid; else l = mid+1; } return hull[l].eval(x); } }; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vc<int> t(n); rep(i, 0, n) cin >> t[i]; rep(i, 1, n) mxto(t[i], t[i-1]); __int128 ans = 0; CHT cht; rep(i, n-1, -1) { cht.add(-(__int128)t[i], (__int128)t[i]*n+ans); ans = cht.query(i); } cout << (int)ans; }