Cutting the puzzle

Time limit2sMemory limit256 MB

Summary

Given the heights of a histogram, find the area of the largest axis-aligned rectangle contained in it.

Level: Medium6 of 10
Topics: Stack, Array
Solved: No attempts yet

Problem

Sangryul has a pile of plastic puzzle pieces shaped like histograms. He no longer needs the puzzles and planned to throw them away, but he suddenly needs a lot of flat plastic. So he decided to cut rectangles out of a puzzle and reuse them.

A histogram is given by the heights of the rectangles that make it up. Every rectangle has width 1, and their bases sit side by side on one straight line. The rectangle you cut out must have its sides parallel to the axes, and it must fit entirely inside the puzzle.

Given the shape of the puzzle, write a program that finds the area of the largest rectangle that can be cut out.

Input

The first line contains the number of rectangles $N$ ( $1 \le N \le 100{,}000$ ) that make up the histogram. Each of the next $N$ lines contains the height $H_i$ ( $1 \le H_i \le 1{,}000{,}000$ ) of one rectangle, given from left to right, one per line.

Output

Print the maximum area of a rectangle that can be cut out on the first line. The answer can exceed the range of a 32-bit integer.

Examples7

Example 1
Input
```
3
7
3
4
```
Expected output
```
9
```
Example 2
Input
```
1
1
```
Expected output
```
1
```
Example 3
Input
```
1
1000000
```
Expected output
```
1000000
```
Example 4
Input
```
5
1
2
3
4
5
```
Expected output
```
9
```
Example 5
Input
```
5
5
4
3
2
1
```
Expected output
```
9
```
Example 6
Input
```
3
2
1
2
```
Expected output
```
3
```
Example 7
Input
```
7
6
2
5
4
5
1
6
```
Expected output
```
12
```