#include<bits/stdc++.h> #define ll long long #define fi first #define se second #define pb push_back #define ii pair<ll,ll> #define iii pair<ll,ii> #define all(a) a.begin(),a.end() using namespace std; const int N=1e6+5; const int mod=1e9+7; const ll inf=1e18+8; ll n,m,k,i,j,q,t; ll tot,dk,tot1=0; ll a[N],dp[N],l[N],r[N]; struct Line { mutable ll m, c, p; bool operator<(const Line& o) const { return m < o.m; } bool operator<(ll x) const { return p < x; } }; // Max CHT struct CHT : multiset<Line, less<>> { const ll INF = LLONG_MAX; ll div(ll a, ll b) { // Floored division return a / b - ((a ^ b) < 0 && a % b); } bool isect(iterator x, iterator y) { if (y == end()) return x->p = INF, 0; if (x->m == y->m) x->p = (x->c > y->c ? INF : -INF); else x->p = div(y->c - x->c, x->m - y->m); return x->p >= y->p; } void add(ll m, ll c) { auto z = insert({m, c, 0}), y = z++, x = y; while (isect(y, z)) z = erase(z); if (x != begin() && isect(--x, y)) isect(x, y = erase(y)); while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y)); } ll query(ll x) { assert(!empty()); auto l = *lower_bound(x); return l.m * x + l.c; } }cht; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; dp[0]=0; cht.add(0,0); a[0]=-inf; r[n]=n; for(int i=n-1;i>0;i--) r[i]=(a[i]>=a[i+1]?r[i+1]:i); l[1]=1; for(int i=2;i<=n;i++) l[i]=(a[i]>=a[i-1]?l[i-1]:i); for(int i=1;i<=n;i++) { i=r[i]; dp[i]=-cht.query(a[i])+n*a[i]; /// cht.add(-j,dp[j]) cht.add(i,-dp[i]); } cout<<dp[n]; return 0; } /* dp[r[i]]=(dp[j]-j*a[i])+(n+1)*a[i] */