Description

最近，铁道部为了挽回声誉，决定给动车印刷广告，广告是刷在城市的建筑物上的，假设城市里有紧靠着的N个建筑。铁道部决定在上面找一块尽可能大的矩形印刷广告。 我们假设每个建筑物都有一个高度，从左到右给出每个建筑物的高度H1,H2…HN，且0

Input

输入有多组数据，每组的第一行是一个数n (n<= 100,000)，第二行是n个数，分别表示每个建筑物高度H1,H2…HN，且0<Hi<=1,000,000,000。

Output

对于每组数据输出一行，表示该城市能印刷广告的最大面积。

Sample

Input

6
5 8 4 4 8 4

Output

24

Source: LCS