#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

The mayor of a certain city wants to give the buildings a fresh coat of paint.

The city has *n* buildings of equal widths but different heights, there is no space between each building.

Being a cheapskate, the mayor decides that only a SINGLE large rectangular block will be painted across the buildings.

Your task is to find the area of the largest such rectangular block that can be painted.

**NOTE:** Not all buildings must be painted across.

## Input

The input will begin with a single integer *n* (1 ≤ *n* ≤ 1,000,000), which is the number of buildings.

The following line will have *n* integers, giving the heights of the buildings from left to right.

## Output

You are to output the area of the largest rectangular block that can be painted. The area of the block will always fit in a 32-bit integer.## Grading

For 30% of the test cases,*n*≤ 1,000.

## Sample Input 1

7 1 2 2 3 2 1 2

## Sample Output 1

8

## Explanation for Sample Output 1

In the above cityscape, the maximum area is 4*2=8 rectangular units, as shaded in red below:

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 10 | 1s | 32MB | Average |

2 | 0 | 1 | 1s | 32MB | Average |

### Judge Compile Command

g++-7 ans.cpp -o landscape -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512