#include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl "\n" int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll t = 1; //cin >> t; while(t--) { ll n; cin >> n; ll a[n + 1], i; deque<ll>dq; for(i = 1; i <= n; i++) { cin >> a[i]; if(dq.size() == 0 || a[dq.back()] < a[i]) { dq.push_back(i); } } ll prev = dq.size() - 1; ll ans = n * a[dq.back()]; for(i = dq.size() - 2; i >= 0; i--) { ll l = i + 2, r = prev; ll ans1 = i + 1; while(l <= r) { ll mid = (l + r) / 2; ll newval = ans - (dq[mid] - 1) * (a[dq[prev]] - a[dq[mid - 1]]); newval += (n - dq[mid] + 1) * a[dq[mid - 1]]; ll newval1 = ans - (dq[mid - 1] - 1) * (a[dq[prev]] - a[dq[mid - 2]]); newval += (n - dq[mid - 1] + 1) * a[dq[mid - 2]]; if(newval <= newval1) { ans1 = mid; l = mid + 1; } else { r = mid - 1; } } ll newval = ans - (dq[ans1] - 1) * (a[dq[prev]] - a[dq[ans1 - 1]]); newval += (n - dq[ans1] + 1) * a[dq[ans1 - 1]]; //cout << newval << " " << a[dq[i]] << endl; if(newval <= ans) { ans = newval; prev = i; } } cout << ans << endl; } #ifndef ONLINE_JUDGE cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; #endif return 0; } // Author: tryharderforioi100