#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<(const ll x) const {return (p<x); } }; struct CHT : multiset<Line,less<>> { const ll INF=LLONG_MAX; ll div(ll a,ll b) { return a/b-(a%b&&(a^b)<0); } 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)) erase(y); while((y=x)!=begin()&&isect(--x,y)) isect(x,y=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] */