#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5, mod = 1e9 + 7;
const ll inf = 9e18;
int n, a[N], MAX;
ll ans, cur;
vector <pair <int, int>> luu;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
// freopen(".INP", "r", stdin);
// freopen(".OUT", "w", stdout);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
luu.emplace_back(a[1], 1);
ans = cur = MAX = a[1];
// cout << ans << '\n';
for (int i = 2; i <= n; ++i) {
if (a[i] <= MAX) ans += cur, luu.back().second++;
else {
MAX = a[i];
luu.emplace_back(a[i], 1);
cur += a[i];
ans += cur;
}
while ((int)luu.size() > 1) {
int sz = luu.size();
int li = luu[sz - 2].second;
int lj = luu[sz - 1].second;
int Mi = luu[sz - 2].first;
int Mj = luu[sz - 1].first;
if (1LL*Mj*li > 1LL*Mi*(li + lj)) break;
luu.pop_back();
luu.pop_back();
luu.emplace_back(Mj, li + lj);
ans -= 1LL*Mi*(li + lj);
ans += 1LL*Mj*li;
cur -= Mi;
}
// cout << ans << '\n';
}
cout << ans;
}
