#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> ii;
const int N = 1e6;
int n;
int a[N+2], st[N+2];
ll dp[N+2];
struct line {
ll m, c;
ll operator ()(ll x) {
return m*x + c;
}
};
bool greaterFrac(ll a, ll b, ll c, ll d) {
// a/b >= c/d;
if (a/b != c/d) return a/b > c/d;
return (a%b)*d >= (c%d)*b;
}
bool isBad(line a, line b, line c) {
// (c1-c2)/(m2-m1) >= (c2-c3)/(m3-m2)
return greaterFrac(a.c-b.c,b.m-a.m,b.c-c.c,c.m-b.m);
// return greaterFrac(c.c-a.c,a.m-c.m,b.c-a.c,a.m-b.m);
}
struct convexHull {
int sz;
deque<line> dq;
convexHull(): sz(0) {}
void insert(ll m, ll c) {
line cur = {m,c};
while (sz >= 2 && isBad(dq[sz-2],dq[sz-1],cur)) {
dq.pop_back();
sz--;
}
dq.push_back(cur);
sz++;
}
ll query(ll x) {
while (sz >= 2 && dq[0](x) >= dq[1](x)) {
dq.pop_front();
sz--;
}
return dq[0](x);
}
} ch;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
reverse(a+1,a+n+1);
vector<int> st;
for (int i = 1; i <= n; i++) {
while (!st.empty() && a[st.back()] <= a[i]) st.pop_back();
st.push_back(i);
}
int m = st.size();
// cout << m << '\n';
// for (int i : st) cout << i << ' ';
// cout << '\n';
for (int i = 1; i <= m; i++) {
ch.insert(a[st[i-1]],dp[i-1]);
dp[i] = ch.query(st[i-1]);
// cout << dp[i] << ' ';
}
// cout << '\n';
cout << dp[m] << '\n';
return 0;
}
