#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;
int lft[N], rght[N];
namespace CHT {
int card;
struct Ray {
int stop;
int a;
long long b;
};
Ray hull[N];
BufferedStack<tuple<int, int, int, Ray>, N> history;
void init() {
card = 1;
hull[0] = Ray{INF, INF, 0};
}
void insert(int a, long long b) {
int low = 0;
int high = card - 1;
auto intersection = [&](const int i) {
return a == hull[i].a ? n
: clamp((b - hull[i].b) / (hull[i].a - a), 0ll, (long long) n);
};
while (low < high) {
int mid = (low + high + 1) / 2;
if (intersection(mid) >= hull[mid - 1].stop + 1) {
low = mid;
} else {
high = mid - 1;
}
}
history.push({card, low, hull[low].stop, hull[low + 1]});
hull[low].stop = intersection(low);
hull[low + 1] = 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].stop) {
high = mid;
} else {
low = mid + 1;
}
}
long long res = (long long) hull[low].a * x + hull[low].b;
return res;
}
void undo() {
auto [oldcard, low, oldstop, oldray] = history.top();
history.pop();
hull[low].stop = oldstop;
hull[low + 1] = oldray;
card = oldcard;
}
}
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, lft[m]);
CHT::insert(a[m], b);
b = min(b, dnc(m + 1, r, rght[m]));
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];
rght[i] = -1;
while (a[stk.top()] < a[i]) {
rght[i] = stk.top();
stk.pop();
}
lft[stk.top()] = i;
stk.push(i);
}
CHT::init();
dnc(0, n, lft[n]);
return 0;
}
