#include<bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #define int long long const int inf=1e18; struct line{ int m=inf,c; int y(int x){ return m*x+c; } }; struct seg{ int l,r; line opt; seg *lf=0,*rg=0; seg(int x,int y){ l=x,r=y; } void update(line baru){ if(opt.m==inf){ opt=baru; return; } int mid=(l+r)/2; if(opt.y(mid)>baru.y(mid))swap(opt,baru); if(l==r)return; if(baru.m>opt.m){ if(mid==l)return; if(!lf){ lf=new seg(l,mid-1); } lf->update(baru); } else{ if(mid==r)return; if(!rg){ rg=new seg(mid+1,r); } rg->update(baru); } } int query(int x){ int mid=(l+r)/2; int ans=opt.y(x); if(mid==x)return ans; if(mid>=x){ if(!lf)return ans; ans=min(ans,lf->query(x)); } else{ if(!rg)return ans; ans=min(ans,rg->query(x)); } return ans; } }; signed main(){ int n; cin>>n; int a[n+1]; for(int q=1;q<=n;q++){ cin>>a[q]; } vector<int>pos; pos.push_back(0); pos.push_back(1); for(int q=2;q<=n;q++){ if(a[q]>a[pos.back()]){ pos.push_back(q); } } pos.push_back(n+1); int hah=1e9; seg cur(1,hah); int dp[pos.size()]; cur.update({0,0}); for(int q=1;q<pos.size()-1;q++){ int brp=cur.query(a[pos[q]]); brp+=a[pos[q]]*n; dp[q]=brp; cur.update({-(pos[q+1]-1),dp[q]}); } cout<<dp[pos.size()-2]<<endl; }