#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define sadd(a, b) a = Add(a, b)
#define smul(a, b) a = Mul(a, b)
using namespace std;
const int N = 1e6 + 2;
const int mod = 1e9 + 7;
ll a[N], dp[N];
struct Line {
ll a, b;
Line() {
a = b = 1e18;
}
Line(ll aa, ll bb) {
a = aa; b = bb;
}
ll F(int x) {
if (a == 1e18 && b == 1e18) return 1e18;
return a * x + b;
}
}st[4 * N];
void Add(int node, int l, int r, Line lin) {
int mid = l + r >> 1;
bool le = lin.F(l) < st[node].F(l);
bool m = lin.F(mid) < st[node].F(mid);
if (m) swap(st[node], lin);
if (l == r) return;
if (le != m) Add(2 * node, l, mid, lin);
else Add(2 * node + 1, mid + 1, r, lin);
}
ll Get(int node, int l, int r, int x) {
ll ans = st[node].F(x);
if (l == r) return ans;
int mid = l + r >> 1;
if (x <= mid) smin(ans, Get(2 * node, l, mid, x));
else smin(ans, Get(2 * node + 1, mid + 1, r, x));
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= 4 * n; i++) st[i] = Line();
for (int i = 1; i <= n; i++) {
cin >> a[i];
smax(a[i], a[i - 1]);
dp[i] = a[i] * n;
}
ll ans = 1e18;
for (int i = n; i >= 1; i--) {
ll o = Get(1, 1, n, i);
if (o != 1e18) dp[i] += o;
Add(1, 1, n, Line(-a[i], dp[i]));
smin(ans, dp[i]);
}
cout << ans << en;
return 0;
}
