#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;
const LL MAXN=1000005;
const LL INF=1e15;
vector<pii> line;
pii garis[MAXN];
pii tpot(pii satu,pii dua){
pii ret;
ret.first=satu.second-dua.second;
ret.second=dua.first-satu.first;
return ret;
}
bool great(pii x,pii y){
if(x.first/x.second<y.first/y.second)return true;
if(x.first/x.second>y.first/y.second)return false;
return (x.first%x.second)%y.second<=(y.first%y.second)*x.second;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
LL n,a,maxVal=0,last=0;
cin >> n;
garis[1]={-1,0}; //-i,dp[i-1]
for(LL i=1;i<=n;i++){
cin >> a;
if(a>=maxVal){
maxVal=a;
for(LL j=last+1;j<=i;j++){
LL skg=line.size()-1,prev=line.size()-2;
while(skg>0 && great(tpot(garis[j],line[skg]),tpot(garis[j],line[prev]))){
line.pop_back();
skg--;
prev--;
}
line.push_back(garis[j]);
}
last=i;
}
LL x=maxVal;
LL dpVal;
if(line.size()==1)dpVal=1LL*x*line[0].first+line[0].second;
else{
LL ki=1,ka=line.size()-1;
dpVal=INF;
while(ki<=ka){
LL mid=(ki+ka)/2;
LL kiri=1LL*x*line[mid-1].first+line[mid-1].second;
LL kanan=1LL*x*line[mid].first+line[mid].second;
dpVal=min(dpVal,min(kiri,kanan));
if(kanan<kiri)ki=mid+1;
else ka=mid-1;
}
}
dpVal+=(1LL*maxVal*(n+1));
garis[i+1]={-(i+1),dpVal};
}
cout << garis[n+1].second << '\n';
return 0;
}
