#include <bits/stdc++.h>
using namespace std;
const int N = 1000100;
const long long inf = (long long) 1e18;
vector<int> xs;
struct Line {
long long k;
long long n;
Line(long long _k = 0, long long _n = inf) : k(_k), n(_n) {}
long long val(long long x) {
return k * x + n;
}
} seg[8 * N];
void Modify(int id, int l, int r, Line ln) {
int mid = (l + r) >> 1;
if (ln.val(xs[mid]) < seg[id].val(xs[mid])) {
swap(ln, seg[id]);
}
if (l == r) {
return;
}
if (ln.val(xs[l]) < seg[id].val(xs[l])) {
Modify(id * 2, l, mid, ln);
} else {
Modify(id * 2 + 1, mid + 1, r, ln);
}
}
long long Query(int id, int l, int r, int p) {
if (l == r) {
return seg[id].val(xs[p]);
}
int mid = (l + r) >> 1;
if (p <= mid) {
return min(seg[id].val(xs[p]), Query(id * 2, l, mid, p));
} else {
return min(seg[id].val(xs[p]), Query(id * 2 + 1, mid + 1, r, p));
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
xs.push_back(a[i]);
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
int k = (int) xs.size();
vector<long long> dp(n, inf);
int ptr = 0;
int idx = 0;
for (int i = 0; i < n; i++) {
if (a[i] >= a[idx]) {
idx = i;
}
while (ptr <= idx) {
Modify(1, 0, k - 1, Line(n - ptr, (ptr == 0 ? 0LL : dp[ptr - 1])));
ptr += 1;
}
int p = (int) (lower_bound(xs.begin(), xs.end(), a[idx]) - xs.begin());
dp[i] = Query(1, 0, k - 1, p);
}
cout << dp[n - 1] << '\n';
return 0;
}
