#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <limits>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;
// Segment Tree for Range Minimum Query (RMQ)
struct SegTree {
int n;
vector<ll> tree;
SegTree(int n_) : n(n_) {
tree.assign(4*n, INF);
}
void update(int idx, int l, int r, int pos, ll val) {
if(l == r) {
tree[idx] = val;
return;
}
int mid = (l + r) / 2;
if(pos <= mid)
update(2*idx, l, mid, pos, val);
else
update(2*idx+1, mid+1, r, pos, val);
tree[idx] = min(tree[2*idx], tree[2*idx+1]);
}
ll query(int idx, int l, int r, int ql, int qr) {
if(ql > r || qr < l) return INF;
if(ql <= l && r <= qr) return tree[idx];
int mid = (l + r) / 2;
return min(query(2*idx, l, mid, ql, qr),
query(2*idx+1, mid+1, r, ql, qr));
}
void update(int pos, ll val) {
update(1, 0, n-1, pos, val);
}
ll query(int l, int r) {
return query(1, 0, n-1, l, r);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
// We use 1-indexing for T and dp for clarity.
vector<int> T(N+1);
for (int i = 1; i <= N; i++){
cin >> T[i];
}
// Precompute next greater element for indices 1..N.
// next[i] = smallest j > i with T[j] > T[i], or N+1 if none.
vector<int> nxt(N+1, N+1);
stack<int> st;
for (int i = 1; i <= N; i++){
while(!st.empty() && T[st.top()] < T[i]){
nxt[st.top()] = i;
st.pop();
}
st.push(i);
}
// For remaining indices, nxt is already N+1.
// dp[j] = minimal additional cost for customers j+1...N.
// We want dp[0] = answer.
// We work with indices 0..N (dp has size N+1)
vector<ll> dp(N+1, INF);
dp[N] = 0;
// Build segment tree over dp[0..N].
// We will update positions as soon as we compute dp[j].
SegTree seg(N+1);
// Initialize dp[N] at position N.
seg.update(N, dp[N]);
// Process j = N-1 downto 0.
// For a fixed j, we want to consider splitting the interval [j+1, N]
// into a first segment. Let i be the first index of the segment (i = j+1 initially).
// Then for i in a segment where the maximum is constant (say = T[i]),
// candidate cost = (N - j)*T[i] + min_{k in [i, nxt[i]-1]} dp[k].
for (int j = N-1; j >= 0; j--){
ll best = INF;
// i starts at j+1.
int i = j + 1;
while(i <= N){
int r = nxt[i]; // next index where the maximum increases.
// Query the minimum dp value in the range [i, r-1]
ll candidate = (ll)(N - j) * T[i] + seg.query(i, r-1);
best = min(best, candidate);
i = r;
}
dp[j] = best;
seg.update(j, dp[j]);
}
cout << dp[0] << "\n";
return 0;
}
