#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
template<typename T>
ostream& operator+(ostream& out, const vector<T> &vec){
for(const auto &x : vec){
out<<x<<" ";
}
out<<"\n";
return out;
}
template<typename T>
ostream& operator*(ostream& out, const vector<T> &vec){
for(const auto &x : vec){
out+x;
}
return out;
}
template<typename T>
istream& operator>>(istream& in, vector<T> &vec){
for(auto &x : vec){
in>>x;
}
return in;
}
const ll INFLL = 1e18;
void solve(){
int n;
cin>>n;
vector<int> seq(n);
cin>>seq;
vector<ll> dp(n + 1, INFLL);
dp[n] = 0;
for(int i=n-1;i>=0;--i){
ll currmx = 0;
for(int j=i;j<n;j++){
currmx = max(currmx, ll(seq[j]));
dp[i] = min(dp[i], currmx*(n-i) + dp[j+1]);
}
}
cout<<dp[0]<<"\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
