#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 + 1, r = prev;
ll ans1 = -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]];
if(newval <= ans)
{
ans1 = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
if(ans1 == -1)
{
continue;
}
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
