#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define int long long
const int mxn=1e5,mod=1000000007,lg=20,root=1000,inf=1e18;
struct line{int m,c;};
double intersect(line a,line b){return ((b.c-a.c)*1.0/(a.m-b.m)*1.0);}
static bool cmp(pair<int,line>a,pair<int,line>b){return a.f<b.f;}
vector<pair<int,line>>con;
void add(line a){
while(con.size()>1&&(intersect(con.back().s,a)<=(intersect(con[con.size()-1].s,con[con.size()-2].s))))con.pop_back();
if(con.empty())con.pb({0,a});
else con.pb({intersect(con.back().s,a),a});
}
int qry(int x){
auto it=ub(all(con),make_pair(x,line{}),cmp);
it--;
line tmp=(*it).s;
return x*(tmp.m)+tmp.c;
}
/*
dpi =dp(j)+ti*(n-j+1)
*/
int32_t main(){
fastio
int n;cin>>n;
vector<int>v(n+1),p(n+1),dp(n+1,INT_MAX);
dp[0]=0;
for(int i=1;i<=n;i++)cin>>v[i],v[i]=max(v[i-1],v[i]);
add(line{0,0});
for(int i=1;i<=n;i++){
dp[i]=v[i]*n;
//ti(1-j)+dp(j-1)
//-tij+dp(j-1)+ti
add(line{-i,dp[i-1]});
if(i>1)dp[i]=min(dp[i],qry(v[i])+v[i]*(n+1));
}
cout<<dp[n]<<'\n';
}
