//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()
using namespace std;
const int N = 1e6 + 6;
const i128 oo = (i128)1000000000000000000LL * (i128)10000000000LL + 25;
void print(i128 a) {
if(a == 0) return cout << 0, void();
if(a < 0) { cout << '-'; a = -a; }
stack<int> s;
while(a > 0) {
s.push((int)(a % 10));
a /= 10;
}
while(!s.empty()) {
cout << s.top();
s.pop();
}
}
struct Line {
ll a; i128 b;
i128 get(ll x) { return (i128)a * x + b; }
};
struct History {
int node;
Line old_line;
bool had_line;
};
Line tree[N << 2];
bool has_line[N << 2];
vector<History> history_stack;
void add_line(int i, int l, int r, Line newline) {
int mid = (l + r) >> 1;
history_stack.push_back({i, tree[i], has_line[i]});
if(!has_line[i]) {
tree[i] = newline;
has_line[i] = 1;
return;
}
bool better_l = newline.get(l) < tree[i].get(l);
bool better_m = newline.get(mid) < tree[i].get(mid);
if(better_m) swap(tree[i], newline);
if(l == r) return;
if(better_l != better_m) add_line(i << 1, l, mid, newline);
else add_line(i << 1 | 1, mid + 1, r, newline);
}
i128 query_lichao(int i, int l, int r, ll x) {
if(!has_line[i]) return oo;
i128 res = tree[i].get(x);
if(l == r) return res;
int mid = (l + r) >> 1;
if(x <= mid) res = min(res, query_lichao(i << 1, l, mid, x));
else res = min(res, query_lichao(i << 1 | 1, mid + 1, r, x));
return res;
}
void rollback(int target_size) {
while((int)history_stack.size() > target_size) {
History h = history_stack.back();
history_stack.pop_back();
tree[h.node] = h.old_line;
has_line[h.node] = h.had_line;
}
}
struct segMunToRi {
i128 st[N << 2];
void init(int n) {
for(int i = 0; i <= (n << 2); ++i) st[i] = oo;
}
void update(int i, int l, int r, int x, i128 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]);
}
i128 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, a[N];
i128 d[N];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
if(!(cin >> n)) return 0;
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;
stack<int> h_ptr;
st.push(n + 1);
for(int i = n; i >= 1; --i) {
while(!st.empty() && a[st.top()] <= a[i]) {
st.pop();
if(!h_ptr.empty()) {
rollback(h_ptr.top());
h_ptr.pop();
}
}
int j = st.top();
st.push(i);
i128 val_min = it.get(1, 1, n + 1, i + 1, j);
h_ptr.push((int)history_stack.size());
add_line(1, 1, n, {a[i], val_min});
d[i] = query_lichao(1, 1, n, n - i + 1);
it.update(1, 1, n + 1, i, d[i]);
}
i128 ok = d[1];
print(ok);
cout << "\n";
return 0;
}
