Problem F
Largest Pocket

Consider a grid of $1 \times 1$ squares, and suppose $N$ columns, each consisting of zero or more $1 \times 1$ grid-aligned blocks, are arranged in a row, all with the same baseline. A pocket is defined as an empty two-dimensional space located above the baseline and bounded on the left and right by columns, as shown in Figure 1.

Figure 1: Illustration of Sample Input 2, which has $12$ columns, with blocks drawn in different colors. This arrangement forms three pockets, depicted in light purple. Pocket 1, with an area $\textrm{of}~ 7$ square units, is the largest pocket.

More precisely, an empty square belongs to a pocket if moving directly left eventually leads to a column block, and similarly if moving directly right. Two pocket squares belong to the same pocket if it is possible to travel from one to the other without passing through a non-pocket square, where “travel” means applying a sequence of single-square up/down/left/right moves. The area of a pocket is the number of squares it contains.

Given the heights of $N$ columns as described above, compute the area of the largest pocket formed by these columns.

Input

The first line of input contains an integer, $N$ $(1 \leq N \leq 10\, 000),$ denoting the number of columns. This is followed by $N$ lines containing the heights of the columns in left-to-right order, one per line. Each height is an integer between $0$ and $1\, 000\, 000,$ inclusive.

Output

Output a line containing a single integer, the area of the largest pocket. If no pockets are formed by the columns, $\textrm{output}~ 0.$

4
0
2
3
1

0

12
4
0
2
3
4
0
2
2
3
0
1
2

7