Envío 5895

Código

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<n;i++)
#define pb push_back
#define ff first
#define ss second
#include <assert.h>
#define ii pair<int,int>
#define vii vector<ii>
#define lli long long int
#define vi vector<lli>
using namespace std;
ostream& operator<<(ostream& os, const vector<lli> &v){
    for(auto const &i: v){
        os<<i<<" ";
    }
    os<<endl;
    return os;
}


int main(){
	lli n; cin>>n;
	vi a(n);
	for(int i = 0; i<n; i++){
		cin>>a[i];
	}
	stack<lli> q; //left to right
	vi lef(n,0);
	for(int i = 0; i<n; i++){
        while(q.size() > 0 && a[q.top()] >= a[i]){
            q.pop();
        }
        lef[i] = (q.size() ? q.top() +1 : 0);
        q.push(i);
	}
	while(q.size())q.pop();
	vi rai(n,n);
	for(int i = n-1; i>=0; i--){
        while(q.size() > 0 && a[q.top()] >= a[i]){
            q.pop();
        }
        rai[i] = (q.size() ? q.top() - 1 : n-1);
        q.push(i);
	}
	lli ans = 0;
	for(int i = 0; i<n; i++){
        ans = max(ans,(abs(i-lef[i])+1)*a[i]);
        ans = max(ans,(abs(i-rai[i])+1)*a[i]);
	}
	cout<<ans<<endl;
	return 0;
}