#include <bits/stdc++.h> using namespace std; #define int __int128 #define sz(x) (int)x.size() #define all(x) x.begin() , x.end() struct CHT{ deque<pair<int,int>>dq; void add(int e , int f){ while(sz(dq) > 1){ int a = dq[sz(dq)-2].first; int b = dq[sz(dq)-2].second; int c = dq[sz(dq)-1].first; int d = dq[sz(dq)-1].second; if((f-b) * (a-c) <= (a-e) * (d-b))dq.pop_back(); else break; } dq.push_back({e,f}); } int query(int x){ while(sz(dq) > 1){ int a = dq[0].first; int b = dq[0].second; int c = dq[1].first; int d = dq[1].second; if(d-b <= (a-c) * x){ dq.pop_front(); } else break; } return dq[0].first * x + dq[0].second; } } cht; void solve(){ long long n; cin >> n; long long arr[n]; for(int i = 0;i<n;i++)cin >> arr[i]; int maxi = arr[0] , premax[n]; memset(premax , 0 , sizeof(premax)); premax[0] = 1; for(int i = 1;i<n;i++){ if(arr[i] > maxi){ premax[i] = 1; maxi = arr[i]; } } cht.add(n , 0); int dp[n] , ans = 0; for(int i = 0;i<n;i++){ if(premax[i] == 0)continue; int ptr = i+1; while(premax[ptr] == 0)ptr++; ptr--; dp[i] = cht.query(arr[i]); // cout << i << " : " << dp[i] << " , ptr : " << ptr << endl; ans = dp[i]; cht.add(n - ptr - 1 , dp[i]); // cout << "added : " << n-ptr-1 << " " << dp[i] << endl; } cout << (long long)(ans) << endl; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); int testcase=1;//cin >> testcase; while(testcase--)solve(); cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl; }