#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
using ll = long long;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// 1-indexed dizi: a[1..n]
vector<ll> a(n+1);
for (int i = 1; i <= n; i++){
cin >> a[i];
}
// dp[i] = min_{1<=l<=i} { dp[l-1] + max(a[l..i]) }
// dp[0] = 0
vector<ll> dp(n+1, LLONG_MAX);
dp[0] = 0;
// prefix_max[i] = max(a[1..i])
vector<ll> prefix_max(n+1, 0);
for (int i = 1; i <= n; i++){
prefix_max[i] = (i==1 ? a[i] : max(prefix_max[i-1], a[i]));
}
// Stack (indeksler) – bu stack üzerinde, aday partition noktalarını (başlangıç indexleri)
// monotonic (azalan) a[] değerlerine göre tutacağız.
// Yani, stack’in tepesinde en son eklenen, “küçük” bir a[i] olacak.
vector<int> st;
// İşleyelim: i = 1'den n'e kadar
for (int i = 1; i <= n; i++){
// Her partition için; direkt tüm diziyi bir grup olarak almanın maliyeti:
// dp[0] + max(a[1..i]) = 0 + prefix_max[i]
dp[i] = prefix_max[i];
// Bir diğer aday: son elemanı tek başına ayrı grup yapmak:
// dp[i-1] + a[i]
dp[i] = min(dp[i], dp[i-1] + a[i]);
// Şimdi, stack’de tutulan aday partition noktalarını değerlendiriyoruz.
// Burada stack’in tepesinde, son geçerli adayın indeksi var.
// Ama yeni gelen a[i] elemanı, bazı adayları “geçecek” (a[i] daha büyük olduğu sürece),
// çünkü;
// eğer bir aday indeks j için a[j] < a[i] ise,
// o zaman, l = j, max(a[j..i]) = a[i] (çünkü a[i] daha büyük),
// ve maliyet adayı dp[j-1] + a[i] ile güncellenebilir.
while(!st.empty() && a[i] >= a[st.back()]){
int j = st.back();
st.pop_back();
// j pozisyonu artık geçerli değil, fakat
// dp[i] için aday olarak, dp[j-1] + a[i] kullanılabilir.
dp[i] = min(dp[i], dp[j-1] + a[i]);
}
// Eğer stack boş değilse,
// stack.back()'daki indeksten sonraki partition noktasında a[st.back()] daha büyük.
if(!st.empty()){
int j = st.back();
// Bu durumda, eğer l = j,
// cost = dp[j-1] + max(a[j..i]). Fakat max(a[j..i]) = a[j] (çünkü a[j] > a[i] ve stack sayesinde)
dp[i] = min(dp[i], dp[j-1] + a[j]);
}
// i'yi stack'e ekle
st.push_back(i);
}
cout << dp[n] << "\n";
return 0;
}
