//LongvnXD
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
using namespace std;
const int N = 1e6 + 6;
const ll oo = 2e18; // Dùng long long thay cho int128
struct Line {
ll a, b;
ll get(ll x) { return a * x + b; }
};
struct RollbackInfo {
int num_popped;
Line overwritten;
};
// CHT mảng tĩnh để tiết kiệm bộ nhớ
Line hull[N];
int hull_sz = 0;
vector<RollbackInfo> rb_stack;
// Kiểm tra đường l2 vô dụng bằng long double để tránh tràn số khi nhân
bool is_bad(Line l1, Line l2, Line l3) {
return (long double)(l2.b - l1.b) * (l2.a - l3.a) >= (long double)(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--;
// Khôi phục lại phần tử bị ghi đè và số lượng phần tử bị pop trước đó
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);
}
// Segment Tree Min d[i]
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() {
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; // Sentinel lớn để bao quát hết stack
it.update(1, 1, n + 1, n + 1, 0);
stack<int> st;
st.push(n + 1);
for(int i = n; i >= 1; --i) {
// Monotonic Stack tìm range (i, j] mà a[i] là min
while(!st.empty() && a[st.top()] <= a[i]) {
st.pop();
// Rollback CHT mỗi khi pop stack
if(!rb_stack.empty()) rollback();
}
int j = st.top();
st.push(i);
// Lấy min của d trong đoạn mà khối i này quản lý
ll min_prev_d = it.get(1, 1, n + 1, i + 1, j);
// Thêm đường thẳng đại diện cho khối hiện tại
// y = a[i] * x + min_prev_d
add_line({a[i], min_prev_d});
// Query x = n - i + 1
d[i] = query_cht(n - i + 1);
it.update(1, 1, n + 1, i, d[i]);
}
ll ok = d[1];
cout << ok << "\n";
return 0;
}
