#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
constexpr int N = 1e6 + 5;
constexpr int INF = 1e9 + 67;
int n;
int a[N];
int amax[N];
int hull_order;
struct {
int x, i;
long long f;
} hull[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// freopen("input.txt", "r", stdin);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
amax[i + 1] = max(amax[i], a[i]);
}
a[n] = INF;
hull_order = 1;
hull[0] = {INF, 0, 0};
int it = 0;
for (int i = 1; i <= n; i++) {
if (a[i] <= amax[i]) continue;
it = min(it, hull_order - 1);
while (amax[i] > hull[it].x) it++;
long long f = hull[it].f + (long long) (n - hull[it].i) * amax[i];
if (i == n) {
cout << f;
return 0;
}
if (hull_order < 2) {
auto &ray = hull[hull_order - 1];
ray.x = min<long long>((f - ray.f) / (i - ray.i), INF);
hull[hull_order++] = {INF, i, f};
continue;
}
while (true) {
auto &ray = hull[hull_order - 1];
int x = min<long long>((f - ray.f) / (i - ray.i), INF);
if (x > hull[hull_order - 2].x) {
ray.x = x;
hull[hull_order++] = {INF, i, f};
break;
}
hull_order--;
}
}
return 0;
}
