#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int range_rng(int l, int r)
{
return uniform_int_distribution<int>(l,r)(rng);
}
pair<int,int> dp[2005];
int v[2005];
const int inf=1e18;
signed main()
{
/*
ifstream fin("arbore.in");
ofstream fout("arbore.out");
*/
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,i,j,mx;
cin >> n;
for (i=1;i<=n;i++)
{
cin >> v[i];
dp[i].first=inf;
dp[i].second=inf;
}
dp[0].first=0;
dp[0].second=0;
for (i=1;i<=n;i++)
{
mx=-1;
for (j=i;j>=1;j--)
{
mx=max(mx,v[j]);
if (dp[j-1].second+(dp[j-1].first+mx)*(i-j+1)<=dp[i].second)
{
if (dp[j-1].second+(dp[j-1].first+mx)*(i-j+1)<dp[i].second)
{
dp[i].second=dp[j-1].second+(dp[j-1].first+mx)*(i-j+1);
dp[i].first=dp[j-1].first+mx;
}
else
dp[i].first=min(dp[i].first,dp[j-1].first+mx);
}
}
}
cout << dp[n].second;
return 0;
}
