#include <bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int INF = INT_MAX;
struct Line {
int a, b;
mutable int p;
bool operator<(const Line& o) const {
if (o.a == INT_MAX && o.b == INT_MAX) return p < o.p;
return a < o.a;
}
};
int a[1000009], f[1000009], g[1000009], dp[1000009];
struct LineContainer {
multiset<Line> myLC;
int div(int a, int b) {
return a / b - ((a ^ b) < 0 && a % b);
}
bool isect(multiset<Line>::iterator x, multiset<Line>::iterator y) {
if (y == myLC.end()) return x->p = INF, false;
if (x->a == y->a) x->p = (x->b > y->b) ? INF : -INF;
else x->p = div(y->b - x->b, x->a - y->a);
return x->p >= y->p;
}
void add(int a, int b) {
auto x = myLC.insert({ a, b, 0 }), y = next(x);
while (isect(x, y)) y = myLC.erase(y);
if ((y = x) != myLC.begin() && isect(--y, x)) isect(y, myLC.erase(x));
while ((x = y) != myLC.begin() && (--x)->p >= y->p)
isect(x, myLC.erase(y)), y = x;
}
int query(int x) {
Line l = *myLC.lower_bound({ INT_MAX, INT_MAX, x });
return l.a * x + l.b;
}
} cht;
void Solve(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i <= n; i++){
f[i] = f[i - 1];
g[i] = g[i - 1];
if(f[i] < a[i]){
g[i] = i;
f[i] = a[i];
}
dp[i] = f[i] * n;
}
int j = 1;
for(int i = 1; i <= n; i++){
while(j < g[i]){
cht.add(j, -dp[j]);
j++;
}
dp[i] = min(dp[i], f[i] * n - cht.query(f[i]));
}
cout << dp[n];
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int test = 1;
//cin >> test;
while(test--){
Solve();
}
return 0;
}
