题目描述

在“方块城”的主干道上，工程师Aki正在搭建一排 能量防护墙模块。
第 i 个模块的 宽度恒为 1，高度为 $h_i$。所有模块底部都在同一条水平基线上。

Aki想从这排模块中选出一段 连续 的模块，把它们拼成一个矩形防护墙。
很显然，一个有效的矩形防护墙的高度取决于拼成它的矩形中的最小高度。

你的任务是：求能拼出的 最大矩形防护墙面积（面积 = 高度 × 宽度）。

例如： 8 1 8 6 10 4 6 9 2

会选择第2个到第7个模块组成矩形防护墙，此时组成的面积最大，为6x4=24。

输入格式

第一行输入一个整数 n，表示模块数量。

• 1 ≤ n ≤ 100000

第二行输入 n 个整数 h1 ... hn，表示每个模块高度：

• 0 ≤ hi ≤ 1000000000

每个模块宽度均为 1。

输出格式

输出一行一个整数，表示最大矩形面积。

8 
1 8 6 10 4 6 9 2

24