#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int range_rng(int l, int r)
{
return uniform_int_distribution<int>(l,r)(rng);
}
int dp[1000005];
int v[1000005];
const int inf=1e18;
const int lim=1e9;
struct Line
{
int a;
int b;
int eval(int x)
{
return a*x+b;
}
};
struct Node
{
int lson;
int rson;
Line lin;
};
Node emptyNode= {0,0,{0,inf}};
class Lichao
{
public:
int sz;
Node aint[1000005];
void init()
{
sz=0;
aint[0]=emptyNode;
}
void insert_line(Line lin)
{
insert_line(-lim,lim,0,lin);
}
void insert_line(int l, int r, int val, Line lin)
{
int mid;
bool tl,tm,tr;
mid=(l+r)/2;
tm=(lin.eval(mid)<aint[val].lin.eval(mid));
if (tm)
swap(aint[val].lin,lin);
tl=(lin.eval(l)<aint[val].lin.eval(l));
tm=(lin.eval(mid)<aint[val].lin.eval(mid));
tr=(lin.eval(r)<aint[val].lin.eval(r));
if (tl)
{
if (aint[val].lson!=0)
insert_line(l,mid,aint[val].lson,lin);
else
{
sz++;
aint[val].lson=sz;
aint[sz]=emptyNode;
aint[sz].lin=lin;
}
}
else if (tr)
{
if (aint[val].rson!=0)
insert_line(mid+1,r,aint[val].rson,lin);
else
{
sz++;
aint[val].rson=sz;
aint[sz]=emptyNode;
aint[sz].lin=lin;
}
}
}
int query(int l, int r, int val, int x)
{
int ans,mid;
ans=inf;
mid=(l+r)/2;
if (x<=mid)
{
ans=min(ans,aint[val].lin.eval(x));
if (aint[val].lson!=0)
ans=min(ans,query(l,mid,aint[val].lson,x));
}
else
{
ans=min(ans,aint[val].lin.eval(x));
if (aint[val].rson!=0)
ans=min(ans,query(mid+1,r,aint[val].rson,x));
}
return ans;
}
} nsuh;
signed main()
{
/*
ifstream fin("arbore.in");
ofstream fout("arbore.out");
*/
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,i,j,mx,idx;
cin >> n;
for (i=1; i<=n; i++)
{
cin >> v[i];
}
nsuh.init();
mx=-1;
idx=0;
for (i=1; i<=n; i++)
{
mx=max(mx,v[i]);
if (v[i]==mx)
{
for (j=idx+1; j<=i; j++)
{
nsuh.insert_line({n-j+1,dp[j-1]});
}
idx=i;
}
dp[i]=nsuh.query(-lim,lim,0,mx);
}
cout << dp[n];
return 0;
}
