#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define F first
#define S second
#define int long long
using namespace std;
const int N = 1e6 + 5, MOD = 1e9 + 7;
int n, a[N], dp[N];
struct Line{
int m, c;
int val(int x){
return m*x + c;
}
};
vector<Line> hulls;
bool check(Line a, Line b, Line cc){
__int128 x = (b.c - a.c);
x = x * (a.m - cc.m);
__int128 y = (cc.c - a.c);
y = y * (a.m - b.m);
if(x > y)
return true;
return false;
}
void insert(int mm, int cc){
Line cur;
cur.m = mm;
cur.c = cc;
while(hulls.size() > 1){
if(check(hulls[hulls.size() - 2], hulls[hulls.size() - 1], cur))
hulls.pop_back();
else
break;
}
hulls.pb(cur);
}
int get(int x){
int low = 0, high = (int) hulls.size() - 2, ans = (int) hulls.size() - 1;
while(low <= high){
int mid = (low + high) / 2;
if(hulls[mid].val(x) <= hulls[mid + 1].val(x)){
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
return hulls[ans].val(x);
}
void solve(){
cin >> n;
a[0] = LLONG_MAX;
bool ok = true;
for(int i = 1; i <= n; ++i){
cin >> a[i];
if(a[i] > a[i - 1])
ok = false;
}
if(ok){
cout << a[1] * n << "\n";
return;
}
int mx = 0;
for(int i = 1; i <= n; ++i){
mx = max(mx, a[i]);
insert(n - i + 1, dp[i - 1]);
dp[i] = get(mx);
}
cout << dp[n] << "\n";
}
int32_t main(){
fast;
int t = 1;
// cin >> t;
while(t--)
solve();
return 0;
}
