题解 | #选区间#

from sys import prefix
from itertools import accumulate
N = int(input())
arr = list(map(int, input().split())) + [0]

res = 0
stack_index = []
prefix_sum = [0]
for i , v in enumerate(arr):
    while stack_index and arr[stack_index[-1]] > v:
        idx = stack_index.pop()
        mmin = arr[idx]
        #积累的就是prefix_sum[i]
        #TODO 弹出的prefix_sum[i] 如果更小
        accumulate = prefix_sum[i] if not stack_index else prefix_sum[i] - prefix_sum[stack_index[-1] + 1]
        res = max(res,mmin * accumulate)
    
    stack_index.append(i)
    prefix_sum.append(prefix_sum[-1] + v)
print(res)