#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ull unsigned ll
#define pb push_back
#define mp make_pair
using namespace std;
int n;
int m;
ll a[1501];
ll mx[1501][1501];
ll dp[1501];
bool check1(){
for(int i=2;i<=n;i++)if(a[i]<a[i-1])return false;
return true;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
if(check1()){
for(int i=1;i<=n;i++){
dp[i]=LLONG_MAX;
for(int j=1;j<=i;j++){
dp[i]=min(dp[i],dp[j-1]+a[i]*(n-j+1));
}
}
cout<<dp[n];
return 0;
}
for(int i=1;i<=n;i++){
ll mxx=-1;
for(int j=i;j<=n;j++){
mxx=max(a[j],mxx);
mx[i][j]=mxx;
}
}
for(int i=1;i<=n;i++){
dp[i]=LLONG_MAX;
for(int j=1;j<=i;j++){
dp[i]=min(dp[i],dp[j-1]+mx[j][i]*(n-j+1));
}
}
cout<<dp[n];
return 0;
}
