#include <bits/stdc++.h>
typedef long long ll;
struct Line {
ll m, b;
Line() {}
Line(ll m, ll b) : m(m), b(b) {}
ll operator()(ll x) { return m * x + b; }
};
class SparseTable {
public:
ll maxPow;
std::vector<ll> orig;
std::vector<std::vector<ll>> table_max;
SparseTable(const std::vector<ll> &x) {
orig = x;
const ll n = x.size();
maxPow = std::floor(std::log2(n));
table_max = std::vector<std::vector<ll>>(maxPow + 1, std::vector<ll>(n));
for (ll i = 0; i < n; ++i) {
table_max[0][i] = x[i];
}
for (ll power = 1; power <= maxPow; ++power) {
for (ll i = 0; i < n - (1 << (power - 1)); ++i) {
table_max[power][i] =
std::max(table_max[power - 1][i],
table_max[power - 1][i + (1 << (power - 1))]);
}
}
}
ll query_max(ll a, ll b) {
if (a == b) {
return orig[a];
}
ll powToUse = std::ceil(std::log2(b - a + 1)) - 1;
return std::max(table_max[powToUse][a],
table_max[powToUse][b - (1 << powToUse) + 1]);
}
};
class CHT {
private:
long double x_intersect(const Line &l1, const Line &l2) {
return -(l1.b - l2.b) / ((long double)(l1.m - l2.m));
}
public:
std::deque<Line> dq;
void insert(Line l) {
while (dq.size() > 1 &&
x_intersect(dq[0], dq[1]) <= x_intersect(dq[0], l)) {
dq.pop_front();
}
dq.push_front(l);
}
ll query(ll x) {
while (dq.size() > 1 && dq[dq.size() - 1](x) <= dq[dq.size() - 2](x)) {
dq.pop_back();
}
return dq.back()(x);
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
ll n;
std::cin >> n;
std::vector<ll> a(n);
for (auto &i : a) {
std::cin >> i;
}
std::vector<bool> active(n);
std::vector<ll> val(n);
for (ll i = 0, mx = 0; i < n; ++i) {
if (a[i] > mx) {
mx = a[i];
val[i] = mx;
active[i] = true;
}
}
for (ll i = 0, prev = -1; i < n; ++i) {
if (active[i]) {
std::swap(prev, val[i]);
}
}
std::vector<ll> dp(n);
ll suff_max = 0;
ll j = -1;
SparseTable table(a);
CHT convex_hull;
for (ll i = n - 1; i >= 0; --i) {
suff_max = std::max(suff_max, a[i]);
dp[i] = suff_max * (n - i);
if (!convex_hull.dq.empty()) {
dp[i] = std::min(dp[i], -convex_hull.query(i));
}
if (j != -1) {
dp[i] = std::min(dp[i], table.query_max(i, j - 1) * (n - i) + dp[j]);
}
if (active[i]) {
if (j != -1) {
// = (-val) * i + dp[j] + val * n
ll m = -val[j];
ll b = dp[j] + val[j] * n;
// insertion is now largest to smallest based on slope
convex_hull.insert({-m, -b});
}
j = i;
}
}
std::cout << dp[0] << '\n';
}
