#include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define setIO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int) (x).size()
#define lc(i) 2*i
#define rc(i) 2*i+1
#define int long long
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vii = vector<ii>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vvb = vector<vb>;
const int N = 1e9 + 5, MOD = 1e9 + 7, INF = 1e17;
template<typename T>
struct LiChaoTree {
struct Line {
T slope, yIntercept;
Line() {
slope = 0;
yIntercept = INF;
}
Line(T slope, T yIntercept) : slope(slope), yIntercept(yIntercept) {}
T val(T x) {
return slope * x + yIntercept;
}
};
struct Node {
int left, right;
Line line;
Node() {
left = -1;
right = -1;
}
T val(T x) { return line.val(x); }
};
T n;
vector<Node> t;
void init(T n) {
this->n = n;
t.clear();
t.emplace_back();
t.emplace_back();
}
void create_children(int i) {
if (t[i].left > -1) return;
t[i].left = sz(t);
t.emplace_back();
t[i].right = sz(t);
t.emplace_back();
}
void insert(int i, T l, T r, Line newLine) {
T mid = (l + r) >> 1;
if (newLine.val(mid) < t[i].val(mid)) swap(newLine, t[i].line);
if (r - l <= 1) return;
create_children(i);
if (newLine.val(l) <= t[i].val(l)) insert(t[i].left, l, mid, newLine);
else insert(t[i].right, mid + 1, r, newLine);
}
T query(int i, T l, T r, T x) {
if (r - l <= 1) return t[i].val(x);
create_children(i);
T mid = (l + r) >> 1;
if (x <= mid) return min(t[i].val(x), query(t[i].left, l, mid, x));
else return min(t[i].val(x), query(t[i].right, mid + 1, r, x));
}
void insert(T slope, T yIntercept) { insert(1, 0, n - 1, Line(slope, yIntercept)); }
T query(T x) { return query(1, 0, n - 1, x); }
};
signed main() {
FAST_IO;
#ifdef arujbansal_local
setIO("input.txt", "output.txt");
#endif
int n;
cin >> n;
int a[n + 1];
for (int i = 1; i <= n; i++) cin >> a[i];
LiChaoTree<int> cht;
cht.init(N);
vi dp(n + 1);
dp[1] = a[1] * n;
cht.insert(n, 0);
int mx = a[1];
for (int i = 2; i <= n; i++) {
mx = max(mx, a[i]);
cht.insert(n - i + 1, dp[i - 1]);
dp[i] = cht.query(mx);
}
cout << dp[n];
}
