#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;
}
struct lines
{
ll a ,b;
lines(ll _a , ll _b )
{
a = _a;
b = _b;
}
ll eval(ll x)
{
return a *x + b;
}
};
deque<lines>adu;
bool bad(lines &l1 , lines &l2 ,lines &l3)
{
return (l3.b - l1.b) * (l1.a - l2.a) < (l2.b - l1.b) * (l1.a - l3.a);
}
void Add(lines x)
{
while((int)adu.size() >= 2 && bad( adu[(int)adu.size()-2] , adu[(int)adu.size()-1] , x ))
{
adu.pop_back();
}
adu.push_back(x);
}
ll Get(ll x)
{
while((int)adu.size() >= 2 && adu[0].eval(x) >= adu[1].eval(x) )adu.pop_front();
return adu[0].eval(x);
}
const int N = 1e6+1;
int n , a[N];
int _next[N];
long long dp[N];
void Input()
{
cin >> n ;
for(int i = 1; i <= n ; i++)
{
cin >> a[i];
if(a[_next[i-1]] <= a[i])_next[i] = i;
else _next[i] = _next[i-1];
}
}
void Process()
{
Add(lines(0 , 0));
for(int i =1 ; i <= n ; i++)
{
if(_next[i] != i)dp[i] = dp[i-1];
else dp[i] = Get(a[i]) + n *1LL * a[i];
Add(lines( -i * 1LL , dp[i] ));
}
cout << dp[n];
}
int main()
{
ios_base :: sync_with_stdio(0);cin.tie(0);
int test = 1;
while(test--)
{
Input();
Process();
}
return 0;
}
