#include<bits/stdc++.h> using namespace std; #define endl '\n' struct line{ long long a,b; }; deque<line> dq; long long interX(line &x,line &y){ return ((y.b-x.b)/(x.a-y.a)); } void add(line &x){ while(dq.size()>=2){ line temp=dq.back(); dq.pop_back(); if(interX(x,temp)>interX(temp,dq.back())){ dq.push_back(temp); break; } } dq.push_back(x); } long long query(int x){ while(dq.size()>=2){ line temp=dq.front(); dq.pop_front(); if(interX(temp,dq.front())>=x){ dq.push_front(temp); break; } } return (1LL*dq.front().a*x+dq.front().b); } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector<pair<int,int>> v; for(int i=0;i<n;i++){ int x; cin >> x; if(v.empty()||x>v.back().first){ v.push_back({x,i}); } } long long DP[v.size()+1]; DP[v.size()]=0; line temp; temp.b=0,temp.a=v.back().first; add(temp); for(int i=v.size()-1;i>=0;i--){ DP[i]=query(n-v[i].second); if(i>0){ temp.b=DP[i],temp.a=v[i-1].first; add(temp); } } cout << DP[0]; }