#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'; }