#include <bits/stdc++.h> using namespace std; #define endl '\n' #define f first // #define s second #define pb(x) push_back(x) #define int long long const int MOD = 1e9+7; const int inf = 1e9; const int INF = 1e18+20; const int LOG = 25; int n; vector<vector<int>> mx; vector<int> dp; int solve (int i) { if (i==n) return 0; if (dp[i]!=-1) return dp[i]; int ans = INF; for (int j=i; j<n; j++) { ans = min(ans, mx[i][j]*(n-i) + solve(j+1)); } return dp[i] = ans; } void solve() { cin>>n; vector<int> a(n); for (int i=0; i<n; i++) cin>>a[i]; mx.resize(n, vector<int>(n)); dp.resize(n+1, -1); for (int i=0; i<n; i++) { int mxi = a[i]; for (int j=i; j<n; j++) { mxi = max(mxi, a[j]); mx[i][j] = mxi; } } cout<<solve(0); } bool multi=false; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t=1; if (multi) cin>>t; while (t--) solve(); return 0; }