CP97 · 柱状图中最大的矩形

较难栈与哈希单调栈时限 1000 ms(参考)
题目描述

给定 n 个宽度为 1 的相邻柱子的高度,求这些柱子能勾勒出的最大矩形面积(矩形必须完全落在柱子内部)。

输入描述

第一行一个整数 n(1 ≤ n ≤ 10^5);第二行 n 个非负整数(高度 ≤ 10^9)。

输出描述

一行,一个整数:最大矩形面积。