Histogram

A histogram is a graph made of bars with equal width. Each bar has an integer height. In the figure below, the heights from left to right are 2, 1, 4, 5, 1, 3, 3.

Find the largest-area rectangle that can be drawn inside the histogram. The base of the rectangle must always be parallel to the bottom side of the histogram, and the whole rectangle must lie inside the area covered by the bars. The shaded region in the figure below is one possible rectangle.

Given a histogram, compute the area of the largest rectangle that can be formed inside it.

The first line contains N, the number of horizontal cells in the histogram. (1 ≤ N ≤ 100,000)

The next N lines contain the heights of the cells from left to right. Each height is an integer from 0 to 1,000,000,000.

Print the area of the largest rectangle that can be formed inside the histogram. The answer does not exceed 2,000,000,000.