#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, a[N], rmq[20][N];
long long dp[N];
deque <int> dq;
int query (int u, int v) {
int k = log2(v - u + 1);
return max(rmq[k][u], rmq[k][v - (1 << k) + 1]);
}
long long cost (int j, int i) {
if (j > n || i > n || j > i) return 0;
return dp[j] + 1LL * query(j + 1, i) * (n - j);
}
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], rmq[0][i] = a[i];
for (int k = 1; k < 20; k++) {
for (int i = 1; i + (1 << k) - 1 <= n; i++) {
rmq[k][i] = max(rmq[k - 1][i], rmq[k - 1][i + (1 << (k - 1))]);
}
}
memset(dp, 0x3f, sizeof(dp)); dp[0] = 0;
dq.push_back(0);
for (int i = 1; i <= n; i++) {
dp[i] = dp[dq.front()] + 1LL * query(dq.front() + 1, i) * (n - dq.front());
while (!dq.empty() && cost(dq.front(), i + 1) > cost(i, i + 1)) dq.pop_front();
while (!dq.empty() && dp[dq.back()] > dp[i]) dq.pop_back();
dq.push_back(i);
}
//for (int i = 1; i <= n; i++) cout << dp[i] << " ";
//cout << "\n";
cout << dp[n] << "\n";
return 0;
}
