#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,O3")
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define se second
#define fi first
#define pii pair<int, int>
#define sz(x) (int)(x).size()
struct Line{
int m, c;
Line(int m, int c) : m(m), c(c) {}
Line() : Line(0, 0) {}
inline int eval(int x){
return m * x + c;
}
inline long double x_int(Line &other){
return (long double)(other.c - c) / (m - other.m);
}
};
inline void solve(){
int n;
cin >> n;
vi t(n + 1), pfmax(n + 1);
for(int i = 1; i <= n; i++){
cin >> t[i];
pfmax[i] = max(t[i], pfmax[i - 1]); // nondecreasing
}
deque<Line> dq;
dq.emplace_back(0, 0);
vi dp(n + 1); // dp[i] = ilk i kişi için olan grupları inceledim finale katkıları: dp[j] + (n - j) * pfmax[i], pfmax'ın o grupta olmadığı durum zaten optimal değil
for(int i = 1; i <= n; i++){
while(sz(dq) >= 2 && dq.front().eval(pfmax[i]) >= dq[1].eval(pfmax[i])){
dq.pop_front();
}
dp[i] = n * pfmax[i] + dq.front().eval(pfmax[i]);
Line line = {-i, dp[i]};
while(sz(dq) >= 2 && line.x_int(dq.back()) <= dq.back().x_int(dq[sz(dq) - 2])){
dq.pop_back();
}
dq.emplace_back(line);
}
cout << dp[n] << "\n";
return;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0;
}
