//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 i128 oo = (i128)1000000000000000000LL * (i128)10000000000LL + 25;
using namespace std;
void print(i128 a) {
if(a == 0) return cout << 0, void();
stack<int> st;
while(a > 0) {
st.push(a % 10);
a /= 10;
}
while(st.size()) cout << st.top(), st.pop();
}
struct Line {
ll a; i128 b; int i;
i128 get(ll x) {
return (i128)a * x + b;
}
};
i128 d[N];
int n, a[N];
struct segMunToRi {
vector<i128> st;
void init(int x) {
st.resize((x << 2) + 2, oo);
}
void update(int i,int l,int r,int x) {
if(l == r) return st[i] = d[x], void();
int mid = l + r >> 1;
if(mid >= x) update(i << 1, l, mid, x);
else update(i << 1 | 1, mid + 1, r, x);
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;
bool is_bad(Line& l1,Line& l2,Line& l3) {
return (i128)(l2.b - l1.b) * (l2.a - l3.a) >= (i128)(l3.b - l2.b) * (l1.a - l2.a);
}
i128 query(ll x,vector<Line>& hull) {
if(hull.empty()) return oo;
int l = 0, r = hull.size() - 2;
while (l <= r) {
int mid = l + (r - l) / 2;
if(hull[mid].get(x) <= hull[mid + 1].get(x))
r = mid - 1;
else
l = mid + 1;
}
return hull[r + 1].get(x);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i], d[i] = oo;
it.init(n + 1);
d[n + 1] = 0;
a[n + 1] = 1e9 + 9;
it.update(1, 1, n + 1, n + 1);
stack<int> st;
st.push(n + 1);
vector<Line> q;
for(int i = n; i; --i) {
while(a[st.top()] <= a[i]) {
int j = st.top(); st.pop();
if(q.size() && q.back().i == j) q.pop_back();
}
int j = st.top();
st.push(i);
i128 Min = it.get(1, 1, n + 1, i + 1, j);
Line line = {a[i], Min, i};
bool push = 1;
while(q.size() && q.back().a == line.a) {
if(q.back().b <= line.b) {
push = 0;
break;
}
q.pop_back();
}
if(push) {
while(q.size() > 1 && is_bad(q[q.size() - 2], q.back(), line)) q.pop_back();
q.push_back(line);
}
d[i] = query(n - i + 1, q);
it.update(1, 1, n + 1, i);
}
print(d[1]);
return 0;
}
