#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#define int long long
const int inf=1e18;
struct line{
int m=inf,c;
int y(int x){
return m*x+c;
}
};
struct seg{
int l,r;
line opt;
seg *lf=0,*rg=0;
seg(int x,int y){
l=x,r=y;
}
void update(line baru){
if(opt.m==inf){
opt=baru; return;
}
int mid=(l+r)/2;
if(opt.y(mid)>baru.y(mid))swap(opt,baru);
if(l==r)return;
if(baru.m>opt.m){
if(mid==l)return;
if(!lf){
lf=new seg(l,mid-1);
}
lf->update(baru);
}
else{
if(mid==r)return;
if(!rg){
rg=new seg(mid+1,r);
}
rg->update(baru);
}
}
int query(int x){
int mid=(l+r)/2;
int ans=opt.y(x);
if(mid==x)return ans;
if(mid>=x){
if(!lf)return ans;
ans=min(ans,lf->query(x));
}
else{
if(!rg)return ans;
ans=min(ans,rg->query(x));
}
return ans;
}
};
signed main(){
int n; cin>>n;
int a[n+1];
for(int q=1;q<=n;q++){
cin>>a[q];
}
vector<int>pos;
pos.push_back(0);
pos.push_back(1);
for(int q=2;q<=n;q++){
if(a[q]>a[pos.back()]){
pos.push_back(q);
}
}
pos.push_back(n+1);
int hah=1e9;
seg cur(1,hah);
int dp[pos.size()];
cur.update({0,0});
for(int q=1;q<pos.size()-1;q++){
int brp=cur.query(a[pos[q]]);
brp+=a[pos[q]]*n;
dp[q]=brp;
cur.update({-(pos[q+1]-1),dp[q]});
}
cout<<dp[pos.size()-2]<<endl;
}
