#include<bits/stdc++.h>
#define int long long
#define _ ((__int128)1)
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e6+10;
int n,a[MAXN],dp[MAXN],tot,pos=1;
struct Node {int x,y;}st[MAXN];
void insert(int x,int y) {
	while(tot>1&&_*(y-st[tot].y)*(st[tot].x-st[tot-1].x)<_*(st[tot].y-st[tot-1].y)*(x-st[tot].x)) tot--;
	return st[++tot]={x,y},void();	
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	ffor(i,1,n) cin>>a[i];
	ffor(i,1,n) a[i]=max(a[i],a[i-1]);
	insert(0,0);
	ffor(i,1,n) {
		while(pos<tot&&_*a[i]*(st[pos+1].x-st[pos].x)>st[pos+1].y-st[pos].y) pos++;
		while(pos>1&&_*a[i]*(st[pos].x-st[pos-1].x)<st[pos].y-st[pos-1].y) pos--;
		dp[i]=n*a[i]+st[pos].y-st[pos].x*a[i];
		insert(i,dp[i]),pos=min(pos,tot);
	}
	cout<<dp[n];
	return 0;
}