#include <bits/stdc++.h>
#define el '\n'
#define FNAME "love"
#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;
namespace 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 getIntersect(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 getIntersect(A,B) >= getIntersect(B,C);
}
inline long long evaluate(long long x){
return a * x + b;
}
};
vector<Line> lines;
vector<double> bubble;
inline void addLine(long long a, long long b){
Line newLine(a,b);
while (lines.size() >= 2 and overlap(lines[lines.size() - 2], lines.back(), newLine)){
lines.pop_back();
bubble.pop_back();
}
if (not lines.empty()){
bubble.push_back(getIntersect(lines.back(), newLine));
}
lines.emplace_back(newLine);
}
inline long long getLine(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;
}
#ifdef LOCAL
#include "../Template/debug.h"
#else
#define debug(...) 15092007
#endif
void sol(){
vector<int> preMax(n + 1,0);
for (int i = 0; i < n; i++) preMax[i + 1] = max(preMax[i], a[i]);
/*
* dp[i] = min(dp[j - 1] + a[i] * (n - j + 1))
* dp[i] = min(dp[j - 1] - a[i] * j) + a[i] * (n + 1)
* dp[i] = min(-a[i] * j + dp[j - 1]) + a[i] * (n + 1)
*/
vector<long long> dp(n + 1,INF);
dp[0] = 0;
MinHull::addLine(-1, 0);
for (int i = 1; i <= n; i++){
dp[i] = MinHull::getLine(preMax[i]) + 1ll * preMax[i] * (n + 1);
MinHull::addLine(-(i + 1), dp[i]);
}
cout<<dp[n];
}
int main(){
setup();
init();
sol();
}
