#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;
const ll INF = 1e18;
int n, m;
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);
}
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);
// }
ll query(ll x) {
ll ret = INF;
for (int l = 0, r = sz-1; l <= r; ) {
int mid = (l+r)/2;
ret = min(ret,dq[mid](x));
if (mid+1 < sz && dq[mid+1](x) < dq[mid](x)) l = mid+1;
else r = mid-1;
}
return ret;
}
} 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);
for (int i = 1; i <= n; i++) {
while (m > 0 && a[st[m]] <= a[i]) m--;
st[++m] = i;
}
for (int i = 1; i <= m; i++) {
ch.insert(a[st[i]],dp[i-1]);
dp[i] = ch.query(st[i]);
}
cout << dp[m] << '\n';
return 0;
}
