#include<bits/stdc++.h>
using namespace std;
const long long N=999999999999999999LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,f[1000009],dp[1000009],K,B,X,z;
deque <pair <long long, long long > > de;
pair <long long, long long> seg[400009];
deque <pair <long long, pair <long long, long long> > > SEG;
void upd(long long q, long long w, long long rr){
if(q>w) return;
if(seg[rr]==make_pair(-1LL,-1LL)){
SEG.push_back({rr,{seg[rr].first,seg[rr].second}});
seg[rr]={K,B};
return;
}
long long mid=(q+w)/2;
if(seg[rr].first*mid+seg[rr].second>K*mid+B){
SEG.push_back({rr,{seg[rr].first,seg[rr].second}});
swap(seg[rr].first,K);swap(seg[rr].second,B);
}
if(seg[rr].first*q+seg[rr].second>K*q+B){
upd(q,mid-1,rr*2);
}else{
if(seg[rr].first*w+seg[rr].second>K*w+B){
upd(mid+1,w,rr*2+1);
}
}
}
void read(long long q, long long w, long long rr){
if(q>w) return;
if(q==w){
if(seg[rr]!=make_pair(-1LL,-1LL)) z=min(z,seg[rr].first*X+seg[rr].second);
return;
}
long long mid=(q+w)/2;
if(seg[rr]!=make_pair(-1LL,-1LL)) z=min(z,seg[rr].first*X+seg[rr].second);
if(X<mid){
read(q,mid-1,rr*2);
}
if(X>mid){
read(mid+1,w,rr*2+1);
}
}
void rollback(long long q){
while(SEG.size()>q){
seg[SEG.back().first]=SEG.back().second;
SEG.pop_back();
}
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a;
for(i=1; i<=a; i++){
cin>>f[i];
}
for(i=0; i<=a+1; i++) dp[i]=N;
for(i=0; i<=400005; i++){
seg[i]={-1,-1};
}
f[a+1]=N;
dp[a+1]=0;
de.push_back({a+1,0});
for(i=a; i>=1; i--){
while(de.size()>0){
c=de.back().first;d=de.back().second;
if(f[c]<=f[i]){
de.pop_back();
rollback(d);
}else{
break;
}
}
if(de.size()){
c=de.back().first;d=de.back().second;
e=SEG.size();
B=dp[c];K=f[i];
upd(1,a,1);
de.push_back({i,e});
}
z=N;
X=a-i+1;
read(1,a,1);
dp[i]=z;
}
/*for(i=1; i<=a; i++){
cout<<dp[i]<<" ";
}
cout<<"\n";*/
cout<<dp[1];
return 0;
}
