#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]
*/
