#include <bits/stdc++.h> #define ll long long #define int ll using namespace std; mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const int INF = INT_MAX; struct Line { int a, b; mutable int p; bool operator<(const Line& o) const { if (o.a == INT_MAX && o.b == INT_MAX) return p < o.p; return a < o.a; } }; int a[1000009], f[1000009], g[1000009], dp[1000009]; struct LineContainer { multiset<Line> myLC; int div(int a, int b) { return a / b - ((a ^ b) < 0 && a % b); } bool isect(multiset<Line>::iterator x, multiset<Line>::iterator y) { if (y == myLC.end()) return x->p = INF, false; if (x->a == y->a) x->p = (x->b > y->b) ? INF : -INF; else x->p = div(y->b - x->b, x->a - y->a); return x->p >= y->p; } void add(int a, int b) { auto x = myLC.insert({ a, b, 0 }), y = next(x); while (isect(x, y)) y = myLC.erase(y); if ((y = x) != myLC.begin() && isect(--y, x)) isect(y, myLC.erase(x)); while ((x = y) != myLC.begin() && (--x)->p >= y->p) isect(x, myLC.erase(y)), y = x; } int query(int x) { Line l = *myLC.lower_bound({ INT_MAX, INT_MAX, x }); return l.a * x + l.b; } } cht; void Solve(){ int n; cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i]; } for(int i = 1; i <= n; i++){ f[i] = f[i - 1]; g[i] = g[i - 1]; if(f[i] < a[i]){ g[i] = i; f[i] = a[i]; } dp[i] = f[i] * n; } int j = 1; for(int i = 1; i <= n; i++){ while(j < g[i]){ cht.add(j, -dp[j]); j++; } dp[i] = min(dp[i], f[i] * n - cht.query(f[i])); } cout << dp[n]; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int test = 1; //cin >> test; while(test--){ Solve(); } return 0; }