#include<bits/stdc++.h>
using namespace std;
#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define fi first
#define se second
#define ll long long
#define eb emplace_back
#define pb push_back
#define __builtin_popcount __builtin_popcountll
#define _ << " " <<
template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}
const int N=1e6+5;
const ll INF=1e18;
int n,t[N]; ll dp[N];
ii stk[N]; int top;
ll minDP[N];
struct Line{
ll a,b;
Line(ll _a=INF, ll _b=INF) : a(_a), b(_b) {}
ll val(ll x){
return a*x + b;
}
};
struct Node{
Line ln;
int lc,rc;
Node(){
ln=Line();
lc=rc=0;
}
};
vector<Node> tr(2);
vector<pair<int,Line>> roll;
void upd(Line ln, int id=1, int l=1, int r=n){
int mid=(l+r)>>1;
if(ln.val(mid)<tr[id].ln.val(mid)){
roll.eb(id,tr[id].ln);
swap(ln,tr[id].ln);
}
if(l==r || ln.b==INF) return;
if(ln.val(l)<tr[id].ln.val(l)){
if(tr[id].lc==0) tr[id].lc=sz(tr), tr.eb();
upd(ln,tr[id].lc,l,mid-1);
} else{
if(tr[id].rc==0) tr[id].rc=sz(tr), tr.eb();
upd(ln,tr[id].rc,mid+1,r);
}
}
ll get(int x, int id=1, int l=1, int r=n){
if(tr[id].ln.b==INF) return INF;
int mid=(l+r)>>1;
return min(tr[id].ln.val(x), x<=mid ? get(x,tr[id].lc,l,mid-1) : get(x,tr[id].rc,mid+1,r));
}
void rollback(int x){
while(sz(roll)>x){
tr[roll.back().fi].ln=roll.back().se;
roll.pop_back();
}
}
void solve(){
cin>>n;
foru(i,1,n) cin>>t[i];
memset(dp,0x3f,sizeof(dp));
dp[n+1]=0;
ford(i,n,1){
minDP[i]=dp[i+1];
while(top && t[stk[top].fi]<t[i]){
mini(minDP[i], minDP[stk[top].fi]);
--top;
}
rollback(stk[top].se);
upd(Line(t[i],minDP[i]));
++top; stk[top]={i,sz(roll)};
dp[i]=get(n-i+1);
}
cout<<dp[1]<<'\n';
}
int32_t main(){
#define task "test"
if(fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
cin.tie(0)->sync_with_stdio(0);
int tc=1; //cin>>tc;
foru(i,1,tc){
solve();
}
}
