#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const int N=2000;
ll a[N];
ll dp[N];
vector<int> ms;
vector<ll> vv;
ll getmin(int i)
{
// a[ms[]] is decreasing
int sz=ms.size();
while(sz>1 and a[ms[sz-1]]*i+vv[sz-1] > a[ms[sz-2]]*i+vv[sz-2]){
ms.pop_back();
vv.pop_back();
sz--;
}
return a[ms[sz-1]]*i+vv[sz-1];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
a[0]=0;
for(int i=1;i<=n;i++)cin>>a[n+1-i],dp[i]=1e18;
dp[0]=0;
ms.push_back(1);
vv.push_back(0);
for(int i=1;i<=n;i++)
{
ll mi=dp[i-1];
while(ms.size()>0 and a[ms.back()]<=a[i])
{
mi=min(mi,vv.back());
ms.pop_back();
vv.pop_back();
}
ms.push_back(i);
vv.push_back(mi);
dp[i]=getmin(i);
}
// for(int i=0;i<n;i++)
// {
// ll mx=0;
// for(int j=i+1;j<=n;j++)
// {
// mx=max(mx,a[j]);
// dp[j]=min(dp[j],dp[i]+1ll*mx*j);
// }
// }
cout<<dp[n]<<endl;
}
