题目描述

最近，afy 决定给 TOJ 印刷广告，广告牌是刷在城市的建筑物上的，城市里有紧靠着的 $N$ 个建筑。

afy 决定在上面找一块尽可能大的矩形放置广告牌。我们假设每个建筑物都有一个高度，从左到右给出每个建筑物的高度 $H_1,H_2,\dots,H_N$ ，且 $0 < H_i ≤ 10^9$ ，并且我们假设每个建筑物的宽度均为 $1$ 。

要求输出广告牌的最大面积。

输入

第一行是一个整数 $n$ ($n \le 400,000$ ）。

第二行是 $n$ 个数，分别表示每个建筑物高度 $H_1,H_2,\dots,H_N$ ，且 $0 < H_i ≤ 10^9$ 。

输出

一个整数，表示最大面积。

样例

6
5 8 4 4 8 4

24

说明

【样例解释】

样例数据的中，最大广告牌的安装方法如下图所示。