//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 all(v) v.begin(), v.end()
const int N = 1e6 + 6;
const i128 oo = (i128)1e18 * (i128)1e10 + 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;
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) {
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;
// Kiểm tra line l2 có bị "bad" (bị che bởi l1 và l3) không
bool is_bad(Line& l1, Line& l2, Line& l3) {
// l2 bad nếu giao điểm (l1,l2) >= giao điểm (l2,l3)
// (l2.b - l1.b)/(l1.a - l2.a) >= (l3.b - l2.b)/(l2.a - l3.a)
return (__int128)(l2.b - l1.b) * (l2.a - l3.a) >= (__int128)(l3.b - l2.b) * (l1.a - l2.a);
}
i128 query(ll x, vector<Line>& hull) {
if(hull.empty()) return oo;
if(hull.size() == 1) return hull[0].get(x);
int l = 0, r = hull.size() - 1;
// Tìm vị trí tốt nhất
while(r - l > 1) {
int mid = (l + r) / 2;
if(hull[mid].get(x) > hull[mid + 1].get(x))
l = mid + 1;
else
r = mid;
}
return min(hull[l].get(x), hull[r].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> hull;
for(int i = n; i >= 1; --i) {
// Loại bỏ các phần tử có a[j] <= a[i]
while(a[st.top()] <= a[i]) {
st.pop();
}
int j = st.top();
st.push(i);
// Lấy min từ đoạn [i+1, j]
i128 Min = it.get(1, 1, n + 1, i + 1, j);
Line line = {a[i], Min};
// Xóa các line có hệ số góc bằng nhau nhưng cao điểm hơn
while(!hull.empty() && hull.back().a == line.a) {
if(hull.back().b <= line.b) {
line.b = oo; // Đánh dấu không thêm
break;
}
hull.pop_back();
}
if(line.b < oo) {
// Duy trì convex hull
while(hull.size() >= 2 && is_bad(hull[hull.size() - 2], hull.back(), line)) {
hull.pop_back();
}
hull.push_back(line);
}
// Tính d[i]
d[i] = query(n - i + 1, hull);
// Cập nhật segment tree
it.update(1, 1, n + 1, i);
}
print(d[1]);
cout << '\n';
return 0;
}
