#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define p(x,y) pair<ll,ll>(x,y)
#define BIT(i,x) ((x>>i)&1)
#define MASK(x) (1<<x)
#define ld long double
#define __builtin_popcount __builtin_popcountll
#define pll pair<ll,ll>
template<class T1,class T2>
bool maximize(T1 &x,const T2 &y)
{
if(x<y)
{
x=y;
return 1;
}
return 0;
}
template<class T1,class T2>
bool minimize(T1 &x,const T2 &y)
{
if(x>y)
{
x=y;
return 1;
}
return 0;
}
void online()
{
std::ios_base::sync_with_stdio(0);
cin.tie(0);
}
struct plane
{
struct line
{
ll m,c;
line(ll _m=0,ll _c=0)
{
this->m = _m;
this->c = _c;
}
ll intersect(line &other)
{
return (this->c - other.c + other.m - this->m +1) / (other.m - this->m);
}
ll vl(ll x)
{
return this->m * x + this->c;
}
};
deque<pair<line,ll>> dq;
void insert(ll m,ll c)
{
line nex(m,c);
if(this->dq.empty())
{
this->dq.push_back(pair<line,ll>(nex,0));
return;
}
while(!this->dq.empty())
{
line pre=this->dq.back().fi;
ll x=this->dq.back().se;
if(nex.m==pre.m)
{
if(nex.c>pre.c) return;
}
else if(nex.intersect(pre)>x) break;
this->dq.pop_back();
}
if(this->dq.empty())
{
this->dq.push_back(pair<line,ll>(nex,0));
return;
}
dq.push_back(pair<line,ll>(nex,nex.intersect(dq.back().fi)));
}
ll query(ll x)
{
ll m = this->dq.size();
while(m > 1 && dq[1].se <= x)
{
this->dq.pop_front();
m--;
}
return this->dq.front().fi.vl(x);
}
};
const ll N=1e6+10;
ll n,k;
ll ar[N],f[N],seg[N];
int main()
{
online();
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>ar[i];
}
seg[1]=1;
for(int i=2;i<=n;i++)
{
if(ar[i]>ar[seg[i-1]]) seg[i]=i;
else seg[i]=seg[i-1];
}
plane P;
for(int i=1;i<=n;i++)
{
P.insert(n-i+1,f[i-1]);
f[i]=P.query(ar[seg[i]]);
}
cout<<f[n];
}
