Find the biggest rectangle that can be formed in a given histogram using a series of adjacent bars with heights specified in an array. Assume all bars have the same width of 1 unit for simplicity.

Visual representation for the sample test:

Input

• The first line contains an integer $n$, the number of bars in the histogram.
• The second line contains $n$ integers $h_i$, the bars height in the histogram, from left to right.

Output

• Print the maximum rectangle area.

Constraints

• $1 \le n \le 10^5$.
• $1 \le A_i \le 10^9$.

Example

Input:

6
2 1 5 6 2 3

Output:

10