题目描述

佛山非常重视城市创文工作，准备在季华路安排灯光秀。灯光秀就是要在骨感道路季华路放置一块矩形的电子屏幕，然后在电子屏幕展示各种和创文有关的内容了。

季华路上有 N 个建筑，每个建筑物的宽度为 1 ，高度为 $h_i$。电子屏幕放在季华路的一侧，跨度不限（从某建筑开始，到某栋建筑结束），但高度不能超过其范围内的任何一栋建筑物。为了增加影响力，佛山市政府希望这块电子屏幕越大越好，但是市长并不知道最终这块屏幕有多大，所以请来了陆阳同学帮忙计算。

作为陆阳同学的好帮手，你能一起设计一个程序算出这个最大值吗？

输入格式

第一行是一个整数 n ( n <= 400,000）

第二行是 n 个数 $h_i$ ，分别表示每个建筑物高度，且 0 < $h_i$ ≤ ${10}^9$ 。

输出格式

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

样例

6
5 8 4 4 8 4

24

样例解释

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