#include <bits/stdc++.h>
using namespace std;
template < typename T >
class SegmentTree {
private:
T *Stree;
T *Snum;
long long n;
T NullValue = 0;
T combine(T a, T b) {
return max(a,b);
}
void build(long long idx, long long s, long long e) {
if (s > e)
return;
if (s == e) {
Stree[idx] = Snum[s];
return ;
}
long long m = ( s + e ) / 2;
build( 2 * idx, s, m);
build( 2 * idx + 1, m + 1, e);
Stree[idx] = combine(Stree[2 * idx], Stree[2 * idx + 1] );
return;
}
T queryUtil(long long idx, long long s, long long e, long long l, long long r) {
if (l > e || r < s)
return NullValue;
if (s >= l && e <= r) {
return Stree[idx];
}
long long m = ( s + e ) / 2;
T left = queryUtil(2 * idx, s, m, l, r);
T right = queryUtil(2 * idx + 1, m + 1, e, l, r);
return combine(left, right );
}
public:
SegmentTree(vector<T> a) {
this->n = a.size();
Stree = new T[4 * n + 5];
Snum = new T[n];
for (long long i = 0; i < n; i++) {
Snum[i] = a[i];
}
build(1, 0, n - 1);
}
T query(long long l, long long r) {
return queryUtil(1, 0, n - 1, l - 1, r - 1);
}
};
long long dp[2000][2000];
long long solve(long long idx,long long last,long long n,SegmentTree<long long> &ST) {
if(idx>=n)return 0;
if(dp[idx][last]!=-1) {
return dp[idx][last];
}
if(last>=n) {
dp[idx][last]=ST.query(idx+1,last+1)*(n-idx);
return ST.query(idx+1,last+1)*(n-idx);
}
long long pos1 = ST.query(idx+1,last+1)*(n-idx) + solve(last+1,last+1,n,ST);
long long pos2 = solve(idx,last+1,n,ST);
dp[idx][last]=min(pos1,pos2);
return min(pos1,pos2);
}
bool is_this_subtask4(vector<long long> a) {
reverse(a.begin(),a.end());
return is_sorted(a.begin(),a.end());
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
long long n;
cin >> n;
vector<long long> a(n);
for(long long i = 0 ; i < n ; i++) {
cin >> a[i];
}
if(is_this_subtask4(a)) {
cout << a[0]*n << '\n';
return 0;
}
SegmentTree<long long> ST(a);
memset(dp,-1,sizeof dp);
long long res = solve(0,0,n,ST);
cout << res << '\n';
return 0;
}
