#include <bits/stdc++.h>
#define foreach for
#define in :
using namespace std;
typedef long long ll ;
const int LOG = 18;
const long long base = 31;
const long long MODULO = 1e9+7;
const long long INF = 1e18+1;
template<class X ,class Y>
bool Minimize(X &x , Y y)
{
if(x > y)
{
x = y;
return true;
}
return false;
}
template<class X , class Y>
bool Maximize(X &x , Y y)
{
if(x < y)
{
x = y;
return true;
}
return false;
}
const int N = 1e6+1;
int n , k ;
long long dp[N];
int a[N];
class SegmentedTree
{
private:
vector<pair<long long , long long >>nodes;
public:
SegmentedTree(int _n)
{
nodes.assign(_n * 4 + 1 , make_pair(INF , INF));
}
void Down(int id ,long long lazy)
{
Minimize(nodes[id].first , lazy);
Minimize(nodes[id].second , lazy);
}
void Update(int l ,int r ,int id , int u ,int v ,long long w)
{
if(l > v || u > r)
{
return ;
}
if(u <= l && r <= v)
{
Minimize(nodes[id].first , w);
Minimize(nodes[id].second , w);
return ;
}
int mid = (l+r) >> 1;
Down(id << 1 , nodes[id].second);
Down(id << 1 |1 , nodes[id].second);
nodes[id].second = INF;
Update(l , mid ,id << 1 , u ,v , w);
Update(mid+1 , r , id <<1 |1 , u , v , w);
nodes[id].first = min(nodes[id << 1].first , nodes[id << 1 | 1].first);
}
long long Get(int l,int r ,int id ,int u ,int v)
{
if(l > v || u > r)
{
return INF;
}
if(u <= l && r <= v)
{
return nodes[id].first;
}
int mid = (l+r) >> 1;
Down(id << 1 , nodes[id].second);
Down(id << 1 |1 , nodes[id].second);
nodes[id].second = INF;
return min(Get(l , mid , id << 1 , u , v) , Get(mid+1 , r , id << 1 |1 , u , v));
}
};
int lll[N] ,rr[N];
void Input()
{
cin >> n ;
for(int i = 1; i <= n ; i++)
{
cin >> a[i];
}
}
void Process()
{
SegmentedTree Seg(n);
stack<int>st;
for(int i =1; i <= n ; i++)
{
while(!st.empty() && a[st.top()] <= a[i])
{
st.pop();
}
lll[i] = 1;
if(!st.empty())lll[i] = st.top() + 1;
st.push(i);
}
while(!st.empty())st.pop();
for(int i = n ; i >= 1 ; i--)
{
while(!st.empty() && a[st.top()] <= a[i])st.pop();
rr[i] = n;
if(!st.empty())rr[i] = st.top() -1;
st.push(i);
}
for(int i = 1 ; i <= n ; i++)dp[i] = INF;
for(int i = 1; i <= n ; i++)
{
int maxx = a[i];
for(int j = i ; j>=1 && (n * 1LL * (i - j +1)) <= 1e7 ; j--)
{
Maximize(maxx , a[j]);
Minimize(dp[i] , dp[j-1] + maxx * 1LL * (n - j + 1));
}
if(a[lll[i] -1] > a[i])
Minimize(dp[i] , dp[lll[i] -1]);
}
cout << dp[n];
}
int main()
{
ios_base :: sync_with_stdio(0);cin.tie(0);
int test = 1;
while(test--)
{
Input();
Process();
}
return 0;
}
