#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool comcross(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c){
return (c.second - a.second) * (b.first - c.first) >= (c.second - b.second) * (a.first - c.first);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
ll n;cin>>n;
vector<ll> A(n); for(ll &i:A) cin>>i;
vector<ll> suf(n);
suf[0] = A[0];
for(ll i=1;i<n;i++){
suf[i] = max(suf[i-1], A[i]);
}
vector<ll> dp(n, LONG_LONG_MAX);
deque<pair<ll, ll>> cht;
dp[n-1] = n*suf[n-1];
cht.push_front({-suf[n-1], dp[n-1]});
auto x_int = [&](pair<ll, ll> &a, pair<ll, ll> &b) -> long double {
return (long double)(b.second - a.second) / (a.first - b.first);
};
for(ll i=n-2;i>=0;i--){
// for(auto i:cht){
// cout << i.first << ':' << i.second << ' ';
// }
// cout << '\n';
while(cht.size() > 1){
pair<ll, ll> l1 = cht[cht.size() - 1], l2 = cht[cht.size() - 2];
if(l2.first*(i+1) + l2.second <= l1.first*(i+1) + l1.second){
cht.pop_back();
}
else
break;
}
dp[i] = (cht.back().first*(i+1) + cht.back().second) + suf[i]*n;
while(cht.size() >= 1 && cht.front().first == -suf[i]){
if(cht.front().second <= dp[i])
break;
else
cht.pop_front();
}
pair<ll, ll> line = {-suf[i], dp[i]};
while(cht.size() > 1 && x_int(cht.front(), line) >= x_int(cht.front(), cht[1]))
cht.pop_front();
cht.push_front({-suf[i], dp[i]});
}
ll mn=LONG_LONG_MAX;
for(ll i:dp){
// cout << i << ' ';
mn = min(mn, i);
}
cout << mn << '\n';
}
