// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int N = 1e6 + 5;
ll n, a[N], dp[N];
ll inf = 1e15;
struct Line {
ll k;
ll b;
ll val(ll x) {
return k *x + b;
}
pair < ll , ll > intr(Line yo) {
ll one = yo.b - b;
ll two = k - yo.k;
if (two < 0) one *= -1, two *= -1;
return {one, two};
}
};
vector < Line > dq;
inline void upd(ll k, ll b) {
Line lin = {k, b};
while (dq.size() > 1) {
Line lina = dq.end()[-1];
Line linb = dq.end()[-2];
pair < ll , ll > A = lin.intr(lina);
pair < ll , ll > B = lina.intr(linb);
if (A.f / A.s <= B.f / B.s) {
dq.pop_back();
}
else break;
}
dq.push_back(lin);
}
ll get(ll x) {
int l = 1, r = dq.size() - 1, mid, res = 0;
while (l <= r) {
mid = ((l + r) >> 1);
if (dq[mid - 1].val(x) >= dq[mid].val(x)) {
l = mid + 1, res = mid;
}
else {
r = mid - 1;
}
}
return dq[res].val(x);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (1 < i && a[i - 1] > a[i]) {
a[i] = a[i - 1];
}
}
dq.push_back({0, 0});
for (int i = 1; i <= n; ++i) {
/*
dp[i] = inf;
for (int j = i - 1; j >= 0; --j) {
dp[i] = min(dp[i], dp[j] - j * a[i] + n * a[i]);
} */
dp[i] = get(a[i]) + n * a[i];
upd(-i, dp[i]);
}
cout << dp[n] << "\n";
}
/*
dp[......]
dp[1..j]
.... j + 1 ... i = max is a[i]
dp[i] = dp[j] + ( n - j ) * a[i]
dp[i] = dp[j] - j * a[i] + n * a[i];
Y = K * X + B
X = a[i]
K = -j;
B = dp[j];
*/
