#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> ipii;
const int MAXN = 1e6+10;
const ll INF = 1e18+10;
const int MOD = 998244353;
const int LOG = 20;
const int ADD = 1e10;
int n, x;
int a[MAXN];
vector <pii> vec;
int dp[MAXN], cnt[MAXN], val[MAXN];
int pr[MAXN];
struct Line {
int m, c;
int getY(int x){
return m*x+c;
}
pii cut(Line oth){
return pii(oth.c-c, m-oth.m);
}
};
vector <Line> ch;
bool cek(Line a, Line b, Line c){
int A = b.cut(a).fi, B = b.cut(a).se;
int C = c.cut(b).fi, D = c.cut(b).se;
// A/B < C/D
if(A/B == C/D){
return (A%B)*D > (C%D)*B;
}
return A/B > C/D;
}
void add(Line nw){
while(ch.size()>=2 &&
!cek(ch[ch.size()-2], ch.back(), nw) ) ch.pop_back();
ch.pb(nw);
// for(auto in : ch) cout << in.m << ' ' << in.c << " mc\n";
// cout << "done\n";
}
int que(int x){
if(ch.size() == 1) return ch[0].getY(x);
int l=1, r=ch.size()-1, mid=0, cnt=INF;
while(r-l>=5){
mid = md;
int le = ch[mid-1].getY(x), ri = ch[mid].getY(x);
cnt = min(cnt, min(le, ri));
if(le > ri) l = mid+2;
else r = mid-2;
}
for(int i=max(0ll,l-1); i<=min(r+1,(int)ch.size()-1); i++)
cnt = min(cnt, ch[i].getY(x));
return cnt;
}
signed main(){
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i];
vec.pb({-1,-1});
for(int i=1; i<=n; i++){
int te = a[i], id = i;
while(i+1<=n && te>=a[i+1]) i++;
vec.pb({te, i-id+1});
}
n = vec.size()-1;
for(int i=1; i<=n; i++){
val[i] = vec[i].fi, cnt[i] = vec[i].se;
pr[i] = pr[i-1] + cnt[i];
}
for(int i=1; i<=n; i++) dp[i] = INF;
Line nw; nw.m = -val[n]; nw.c = val[n]*pr[n];
add(nw);
for(int i=n; i>=1; i--){
dp[i] = que(pr[i-1]);
Line nw; nw.m = -val[i-1]; nw.c = dp[i] + val[i-1]*pr[n];
add(nw);
}
// for(int i=n; i>=1; i--){
// for(int j=i; j<=n; j++){
// dp[i] = min(dp[i], dp[j+1] + val[j]*pr[n] - val[j]*pr[i-1]);
// }
// }
cout << dp[1] << '\n';
}
