#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
const long long inf = 1e16;
long long dp[maxn];
int a[maxn];
int n;
struct hull {
vector <long long> M, C;
int pt;
hull() {
pt = 0;
}
bool bad(int i, int j, int k) {
return (C[k] - C[j]) * (M[i] - M[k]) <= (C[k] - C[i]) * (M[j] - M[k]);
}
void add(long long m, long long c) {
M.push_back(m);
C.push_back(c);
while(M.size() >= 3 && bad(M.size() - 3, M.size() - 2, M.size() - 1)) {
M.erase(M.end() - 2);
C.erase(C.end() - 2);
}
pt = min(pt, int(M.size()) - 1);
}
long long eval(long long x) {
if(M.size() == 0) return inf;
while(pt + 1 < M.size() &&
M[pt] * x + C[pt] >= M[pt + 1] * x + C[pt + 1]) {
++pt;
}
return M[pt] * x + C[pt];
}
} t[maxn * 4];
void update(int x, int c = 1, int b = 0, int e = n) {
t[c].add(n - x, dp[x]);
if(b == e) {
return ;
}
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
if(x <= m) update(x, l, b, m);
else update(x, r, m + 1, e);
}
long long query(int x, int y, int val, int c = 1, int b = 0, int e = n) {
if(x <= b && e <= y) {
return t[c].eval(val);
}
if(y < b || e < x) return inf;
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
return min(query(x, y, val, l, b, m), query(x, y, val, r, m + 1, e));
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
vector <int> v ({0});
a[0] = INT_MAX;
update(0);
dp[0] = inf;
for(int i = 1; i <= n; i++) {
while(a[v.back()] <= a[i]) {
v.pop_back();
}
dp[i] = min(dp[v.back()], query(v.back(), n, a[i]));
update(i);
v.push_back(i);
}
printf("%lld\n", dp[n]);
return 0;
}
