#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 ans = n * a[dq.back()]; for(i = dq.size() - 2; i >= 0; i--) { ll newval = ans - (dq[i + 1] - 1) * (a[dq[i + 1]] - a[dq[i]]); newval += (n - dq[i + 1] + 1) * a[dq[i]]; if(newval <= ans) { ans = newval; } else { break; } } cout << ans << endl; } #ifndef ONLINE_JUDGE cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; #endif return 0; } // Author: tryharderforioi100