Histogram

The histogram is a polygon formed from the sequence of rectangles, aligned on a common baseline. The rectangles are of equal width, but may have different heights. For example, the figure on the left shows the histogram, which consists of rectangles with heights of $2,1,4,5,1,3,3$. All rectangles in this figure have a width equal to $1$.

Usually, histograms are used to represent discrete distributions, for example, the frequency of characters in the texts. Note that the order of the rectangles is very important. Calculate the area of the largest rectangle in the histogram, which is also located on a common baseline. The figure on the right is the shaded figure is equal to the largest aligned rectangle on the image histogram.

Input

First line contains the number $n(0\le n\le 10^6)$ of rectangles of the histogram. This is followed by $n$ integers $h_1,...,h_n(0\le h_i\le 10^9)$. These numbers indicate the height of the rectangle of the histogram from left to right. The width of each rectangle is equal to $1$.

Output

Print the area of the largest rectangle in the histogram. Remember that this rectangle should be on a common baseline.

Examples