Given an array of non-negative integers heights, where each element represents the height of a histogram bar and the width of every bar is 1, find the area of the largest rectangle that can be formed within the histogram.

Return the maximum possible rectangular area.

Input

The first line contains an integer n, representing the number of bars in the histogram.

The second line contains n integers heights[i], representing the height of each bar.

Output

Print a single integer representing the area of the largest rectangle in the histogram.

Example 1

Input

6
2 1 5 6 2 3

Output

10

Explanation

The above is a histogram where width of each bar is 1.

The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2

Input

2
2 4

Output

4