#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
template <class Value, size_t MAX_SIZE>
class BufferedStack {
Value buf[MAX_SIZE];
Value *end = buf;
public:
inline bool empty() const { return end == buf; }
inline void push(const Value &value) { *++end = value; }
inline void pop() { --end; }
inline Value top() const { return *end; }
};
constexpr int N = 1e6 + 5;
constexpr int INF = 1e9 + 67;
int n;
int a[N];
BufferedStack<int, N> stk;
pair<int, int> tree[N];
namespace CHT {
int card;
struct Ray {
int stop;
int a;
long long b;
};
stack<Ray> hull[N];
stack<tuple<int, int, int>> history;
void init() {
card = 1;
hull[0].push(Ray{INF, INF, 0});
}
void insert(int a, long long b) {
// cout << "inserts y = " << a << "x + " << b << endl;
int low = min(1, card - 1);
int high = card - 1;
auto intersection = [&](const int i) {
return a == hull[i].top().a ? n
: clamp((b - hull[i].top().b) / (hull[i].top().a - a), 0ll, (long long) n);
};
while (low < high) {
int mid = (low + high + 1) / 2;
if (intersection(mid) >= hull[mid - 1].top().stop + 1) {
low = mid;
} else {
high = mid - 1;
}
}
history.emplace(card, low, hull[low].top().stop);
hull[low].top().stop = intersection(low);
hull[low + 1].push(Ray{INF, a, b});
card = low + 2;
}
long long query(int x) {
int low = 0;
int high = card - 1;
while (low < high) {
int mid = (low + high) / 2;
if (x <= hull[mid].top().stop) {
high = mid;
} else {
low = mid + 1;
}
}
long long res = (long long) hull[low].top().a * x + hull[low].top().b;
// cout << "query " << x << " -> " << res << endl;
return res;
}
void undo() {
auto [oldcard, low, stop] = history.top();
history.pop();
hull[low].top().stop = stop;
hull[low + 1].pop();
card = oldcard;
// cout << "undo" << endl;
}
}
long long dnc(int l, int r, int m) {
if (l >= r) {
if (l == n) {
cout << CHT::query(l);
exit(0);
}
return l ? CHT::query(l) : 0;
}
long long b = dnc(l, m, tree[m].first);
// cout << "[" << l << ", " << m << "] -> [" << m + 1 << ", " << r << "]" << endl;
CHT::insert(a[m], b);
b = min(b, dnc(m + 1, r, tree[m].second));
CHT::undo();
return b;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// freopen("input.txt", "r", stdin);
cin >> n;
a[n] = INF;
stk.push(n);
for (int i = n - 1; i >= 0; i--) {
cin >> a[i];
tree[i].second = -1;
while (a[stk.top()] < a[i]) {
tree[i].second = stk.top();
stk.pop();
}
tree[stk.top()].first = i;
stk.push(i);
}
CHT::init();
dnc(0, n, tree[n].first);
return 0;
}
