题目描述

最近，afy决定给TOJ印刷广告，广告牌是刷在城市的建筑物上的，城市里有紧靠着的$\red {N}$个建筑。afy决定在上面找一块尽可能大的矩形放置广告牌。我们假设每个建筑物都有一个高度，从左到右给出每个建筑物的高度$\red {H_1,H_2…H_N}$，且$\red {0<H_i<=1,000,000,000}$，并且我们假设每个建筑物的宽度均为$\red {1}$。要求输出广告牌的最大面积。

输入格式

第一行是一个数$\red {n (n≤ 400,000 ）}$第二行是$\red {n}$个数，分别表示每个建筑物高度$\red {H_1,H_2…H_N}$，且$\red {0<H_i<≤1,000,000,000}$。

输出格式

中一共有一行，表示广告牌的最大面积。

样例

输入样例

6                     

5 8 4 4 8 4

输出样例

24