//LongvnXD
#include <bits/stdc++.h>
#define i128 __int128_t
#define ll long long
#define pll pair<ll, ll>
#define ii pair<int, int>
#define fi first
#define se second
#define x first
#define y second
#define all(v) v.begin(), v.end()
const int N = 1e6 + 6;
const ll oo = 1e18 + 18;
using namespace std;
struct Line {
ll a, b;
ll get(ll x) { return a * x + b; }
};
struct RollbackInfo {
int num_popped;
Line overwritten;
};
Line hull[N];
int hull_sz = 0;
vector<RollbackInfo> rb_stack;
bool is_bad(Line l1, Line l2, Line l3) {
return (__int128_t)(l2.b - l1.b) * (l2.a - l3.a) >= (__int128_t)(l3.b - l2.b) * (l1.a - l2.a);
}
void add_line(Line nl) {
int popped = 0;
while(hull_sz >= 2 && is_bad(hull[hull_sz - 2], hull[hull_sz - 1], nl)) {
hull_sz--;
popped++;
}
RollbackInfo info = {popped, hull[hull_sz]};
hull[hull_sz++] = nl;
rb_stack.push_back(info);
}
void rollback() {
RollbackInfo info = rb_stack.back();
rb_stack.pop_back();
hull_sz--;
hull[hull_sz] = info.overwritten;
hull_sz += info.num_popped;
}
ll query_cht(ll x) {
if(hull_sz == 0) return oo;
int l = 0, r = hull_sz - 2;
int best_idx = hull_sz - 1;
while(l <= r) {
int mid = (l + r) >> 1;
if(hull[mid].get(x) <= hull[mid + 1].get(x)) {
best_idx = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return hull[best_idx].get(x);
}
struct segMunToRi {
ll st[N << 2];
void init(int n) {
fill(st, st + (n << 2) + 1, oo);
}
void update(int i, int l, int r, int x, ll val) {
if(l == r) { st[i] = val; return; }
int mid = (l + r) >> 1;
if(x <= mid) update(i << 1, l, mid, x, val);
else update(i << 1 | 1, mid + 1, r, x, val);
st[i] = min(st[i << 1], st[i << 1 | 1]);
}
ll get(int i, int l, int r, int x, int y) {
if(l > y || r < x) return oo;
if(l >= x && r <= y) return st[i];
int mid = (l + r) >> 1;
return min(get(i << 1, l, mid, x, y), get(i << 1 | 1, mid + 1, r, x, y));
}
} it;
int n;
ll a[N], d[N];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i];
it.init(n + 1);
d[n + 1] = 0;
a[n + 1] = 2e9;
it.update(1, 1, n + 1, n + 1, 0);
stack<int> st;
st.push(n + 1);
for(int i = n; i >= 1; --i) {
while(!st.empty() && a[st.top()] <= a[i]) {
st.pop();
if(!rb_stack.empty()) rollback();
}
int j = st.top();
st.push(i);
ll min_prev_d = it.get(1, 1, n + 1, i + 1, j);
add_line({a[i], min_prev_d});
d[i] = query_cht(n - i + 1);
it.update(1, 1, n + 1, i, d[i]);
}
cout << d[1];
return 0;
}
