eolymp
bolt
Try our new interface for solving problems
Problems

Maximal area

Maximal area

Time limit 1 second
Memory limit 128 MiB

It is well known that building a hotel near sea coast is very profitable. That is why the company International Ocean Investment bought a piece of earth on the Black See coast (similar to shown on the Figure) and would like to build a hotel - as big as possible. By different reasons the hotel has to be with rectangular basement. That is why the company searches somebody to find the rectangle with maximal surface which could be drawn on the piece of earth. For the purpose the terrain was split in n columns of equal squares (white on the Figure). Columns are labeled with 1, 2, ..., n consecutively, from left to right, and the rectangle should be composed of integer number of such squares. Then for each column the number of whole squares in the column was counted.

prb8590.gif

Write a program to find the surface of the maximal rectangle on the terrain that could be composed of squares.

Input data

The first line contains the positive integer n (n10^6). On the next row n integers are given d[1], d[2], ..., d[n], where d[i] (0 < d[i]15000) is the number of squares in the column i.

Output data

Print the found maximal surface.

Examples

Input example #1
11
6 5 2 7 8 6 8 3 5 6 7
Output example #1
24
Source 2015 VII International autumn tournament in informatics, Shumen, Junior, Problem B