#include <bits/stdc++.h>
#define el '\n'
#define FNAME "NOI20_discharging"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9 + 7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}
void setup(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
if (fopen(FNAME".inp","r")){
freopen(FNAME".inp","r",stdin);
freopen(FNAME".out","w",stdout);
}
}
const long long INF = (long long) 1e16 + 15092007;
struct MinHull{
struct Line{
long long a,b;
Line():a(0),b(0) {}
Line(long long A,long long B):a(A),b(B) {}
friend double getIntersection(const Line &x, const Line &y){
return 1.0 * (y.b - x.b) / (x.a - y.a);
}
friend bool overlap(Line A,Line B,Line C){
return getIntersection(B,C) < getIntersection(A,C);
}
long long evaluate(long long x){
return a * x + b;
}
};
vector<Line> lines;
vector<double> bubble;
void addLine(long long a, long long b){
Line newLine = Line(a,b);
while (lines.size() >= 2 and overlap(lines[lines.size()-2], lines.back(), newLine)){
lines.pop_back();
bubble.pop_back();
}
if (!lines.empty()){
bubble.emplace_back(getIntersection(lines.back() , newLine));
}
lines.emplace_back(newLine);
}
long long getVal(long long x){
int pos = lower_bound(allof(bubble),x) - bubble.begin();
return lines[pos].evaluate(x);
}
};
int n;
vector<int> a;
void init(){
cin>>n;
a.resize(n);
for (int &x : a) cin>>x;
for (int i=1;i<n;i++) maximize(a[i],a[i-1]);
}
namespace DPNaive{
void solve(){
vector<long long> dp(n+1,INF);
dp[0] = 0;
for (int i=1;i<=n;i++){
for (int j=i;j>=1;j--){
minimize(dp[i] , dp[j-1] + 1ll * a[i-1] * (n - j + 1));
}
}
cout<<dp[n];
exit(0);
}
};
namespace ConvexHullTrick{
void solve(){
MinHull cht;
vector<long long> dp(n+1,INF);
dp[0] = 0;
cht.addLine(n,dp[0]);
for (int i=1;i<=n;i++){
dp[i] = cht.getVal(a[i-1]);
cht.addLine(n - i + 1, dp[i-1]);
}
cout<<dp[n];
}
};
void sol(){
if (n <= 1000) DPNaive::solve();
ConvexHullTrick::solve();
}
int main(){
setup();
init();
sol();
}
