#include <iostream>
#include <deque>
using namespace std;
#define int long long
const int N = 1<<20;
int dp[N], a[N], p[N], c[N], m[N];
int intersection(int i, int j){
if (m[i] == m[j]){
if (c[i] < c[j])
return N;
return -1e9;
}
int A = c[j] - c[i], B = m[i] - m[j];
// cout<<A<<','<<B<<' ';
return A / B + (A % B != 0 and ((A < 0) ^ (B < 0)) == 0);
}
signed main(){
int n;
cin>>n;
for (int i=1;i<=n;i++){
cin>>a[i];
p[i] = p[i-1];
if (a[i] >= a[p[i-1]])
p[i] = i;
m[i] = -a[p[i]];
}
c[p[n]] = n * a[p[n]];
m[p[n]] = -a[p[n]];
deque<int> v = {p[n]}, en = {n + 1};
for (int i=p[n]-1;i + 1;i--){
while (v.size() > 1 and en[1] > i)
v.pop_front(), en.pop_front();
dp[i] = dp[v[0]] + a[p[v[0]]] * (n - i);
c[i] = dp[i] + a[p[i]] * n;
if (i == 0)
break;
while (v.size() > 0 and intersection(i, v.back()) >= en.back())
v.pop_back(), en.pop_back();
if (v.size() == 0)
v = {i}, en = {n+1};
else if (intersection(i, v.back()) != -1e9){
en.push_back(intersection(i, v.back()));
v.push_back(i);
}
}
cout<<dp[0]<<endl;
}
