//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; // large i128
using namespace std;
void print(i128 a) {
if(a == 0) { cout << 0; return; }
if(a < 0) { cout << '-'; a = -a; }
stack<int> st;
while(a > 0) {
st.push((int)(a % 10));
a /= 10;
}
while(!st.empty()) { cout << st.top(); st.pop(); }
}
struct Line {
ll a; i128 b; int i;
i128 get(ll x) const {
return (i128)a * x + b;
}
};
i128 d[N];
int n, a[N];
struct segMunToRi {
vector<i128> st;
void init(int x) {
st.assign((x << 2) + 5, oo);
}
void update(int i,int l,int r,int x) {
if(l == r) { st[i] = d[x]; return; }
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(const Line& l1,const Line& l2,const 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,const vector<Line>& hull) {
if(hull.empty()) return oo;
int l = 0, r = (int)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() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if(!(cin >> n)) return 0;
for(int i = 1; i <= n; ++i) { cin >> a[i]; d[i] = oo; }
it.init(n + 1);
a[n + 1] = 1000000009; // large sentinel
d[n + 1] = 0; // <-- **CRITICAL** base case
it.update(1, 1, n + 1, n + 1);
stack<int> st;
st.push(n + 1);
vector<Line> q;
for(int i = n; i >= 1; --i) {
while(!st.empty() && a[st.top()] <= a[i]) {
int j = st.top(); st.pop();
if(!q.empty() && 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 = true;
while(!q.empty() && q.back().a == line.a) {
if(q.back().b <= line.b) {
push = false;
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;
}
