#include <bits/stdc++.h>
/*
--> Author: Kazuki_Hoshino__8703 <--
I love Nanasaki Ai ☆*: .｡. o(≧▽≦)o .｡.:*☆
*/
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
using namespace std;
const int mn = 1e6 + 5;
const ll inf = 1e18;
int n, a[mn], prefix[mn], id[mn];
ll dp[mn];
struct line{double x, y; };
double center(line x, line y){
return (x.y - y.y) / (y.x - x.x);
}
vector <line> reina;
vector <double> pts;
void add(line kumiko){
while(reina.size() && reina.back().x == kumiko.x && reina.back().y > kumiko.y){
reina.pop_back();
pts.pop_back();
}
while(reina.size() >= 2 && center(reina.back(), kumiko) <= pts.back()){
reina.pop_back();
pts.pop_back();
}
if(reina.size()) pts.push_back(center(reina.back(), kumiko));
else pts.push_back(-inf);
reina.push_back(kumiko);
}
ll query(int val){
int id = upper_bound(pts.begin(), pts.end(), (double)val) - pts.begin() - 1;
return (ll)reina[id].x * (ll)val + (ll)reina[id].y;
}
void solve(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
prefix[i] = max(prefix[i - 1], a[i]);
}
// dp[i] = dp[j] + prefix_max[i] * (n - j) = min(dp[j] - prefix_max[i] * j) + n * prefix_max[i]
add({0, (double)prefix[0]});
for(int i = 1; i <= n; i++){
dp[i] = query(prefix[i]) + (ll)n * (ll)prefix[i];
add({(double)-i, (double)dp[i]});
}
cout << dp[n];
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t = 1;
// cin >> t;
while(t--){
solve();
}
}
