#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i , a , b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define sz(x) (int)(x).size()
#define BIT(mask , x) (((mask) >> (x)) & (1))
#define MASK(x) ((LL)(1)<<(x))
#define TIME_USED cerr << endl << "TIME LAPSED : " << 1.0 * clock() / CLOCKS_PER_SEC << "s" << endl;
template<class T1 , class T2>
bool maximize(T1 &a , T2 b){
if (a < b) return a = b , true; else return false;
}
template<class T1 , class T2>
bool minimize(T1 &a , T2 b){
if (a > b) return a = b , true; else return false;
}
template<class T>
void compress(vector<T>&data){
sort(data.begin() , data.end());
data.resize(unique(data.begin() , data.end()) - data.begin());
}
template<class T1 , class T2>
T2 Find(const vector<T1>&data , T2 y){
return upper_bound(data.begin() , data.end() , y) - data.begin();
}
const int N = (int) 1e6;
const LL inf = (LL) 1e18;
int n , a[N + 2];
namespace subtask2{
bool check(){
return true;
}
struct Line {
LL a , b , id;
Line(LL a , LL b , LL id) : a(a) , b(b) , id(id) {};
};
class Convex_Hull{
public:
bool cmp1(Line a , Line b , Line c){
LL y1 = (a.a - b.a) , y2 = (a.a - c.a);
LL x1 = (b.b - a.b) , x2 = (c.b - a.b);
return x1 * y2 >= x2 * y1;
}
bool cmp2(Line a , Line b , LL x){
LL y1 = (a.a - b.a);
LL x1 = (b.b - a.b);
return x1 <= x * y1;
}
LL F(Line a , LL x){
return a.a * x + a.b;
}
vector<Line> lines;
int ptr = 0;
void add_line(Line x){
int size = sz(lines);
while (size > 1 && cmp1(lines[size - 2] , lines[size - 1] , x)){
--size;
lines.pop_back();
}
lines.push_back(x);
}
int Find_index(int x){
int low = 0 , high = sz(lines) - 1 , pos = sz(lines);
while (low <= high){
int mid = (low + high) / 2;
if (lines[mid].id >= x) pos = mid , high = mid - 1;
else low = mid + 1;
}
return pos + 1;
}
LL Find(int limit , LL x , bool de = false){
int low = Find_index(limit) , high = sz(lines) - 1;
int pos = low - 1;
while (low <= high){
int mid = (low + high) / 2;
if (cmp2(lines[mid - 1] , lines[mid] , x)){
pos = mid;
low = mid + 1;
}
else high = mid - 1;
}
if (pos == sz(lines)) return inf;
return F(lines[pos] , x);
}
void insert(LL a , LL b , LL id){
add_line(Line(a , b , id));
}
};
Convex_Hull cover;
int lef[N + 2] = {};
LL dp[N + 2] = {};
void main_code(){
vector<int> st;
FOR(i , 1 , n) {
while (st.size() && a[st.back()] <= a[i]) st.pop_back();
if (st.size()) lef[i] = st.back() ; else lef[i] = 0;
st.push_back(i);
}
memset(dp , -0x3f , sizeof dp);
cover.insert(0 , 0 , 0);
dp[0] = 0;
for(int i = 1; i <= n; ++i){
LL t = cover.Find(lef[i] , a[i] , i == 4);
dp[i] = t + (LL)n * a[i];
if (lef[i] != 0) dp[i] = min(dp[i] , dp[lef[i]]);
cover.insert(-i , dp[i] , i);
}
cout << dp[n];
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0);
#define name "main"
if (fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
cin >> n;
FOR(i , 1 , n) cin >> a[i];
if (subtask2::check()) return subtask2::main_code() , 0;
TIME_USED;
}
