Maximal Area

Interview

Time limit2sMemory limit256 MB

Summary

Given N column heights, find the area of the largest rectangle formed by whole unit squares.

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

Problem

Building a hotel near the sea coast is profitable. That is why International Ocean Investment bought a piece of land on the Black Sea coast, similar to the one in the figure, and wants to build a hotel that is as large as possible. For several reasons the base of the hotel has to be a rectangle, so the company wants the rectangle of maximal area that can be drawn on the land.

The terrain is split into $N$ columns of equal squares (white in the figure). The columns are numbered $1, 2, \ldots, N$ from left to right, and the rectangle has to be made of a whole number of these squares. For each column the number of whole squares in that column was counted. Write a program that finds the area of the largest rectangle that can be made of those squares.

Input

The first line contains a positive integer $N$ ( $N \le 1\,000\,000$ ).

The second line contains $N$ integers $D_1, D_2, \ldots, D_N$ , where $D_i$ is the number of squares in column $i$ and $0 < D_i \le 15\,000$ .

Output

Print the maximal area that was found. The value can exceed the range of a 32-bit signed integer.

Examples5

Example 1
Input
```
11
6 5 2 7 8 6 8 3 5 6 7
```
Expected output
```
24
```
Example 2
Input
```
8
2 1 5 6 2 3 1 4
```
Expected output
```
10
```
Example 3
Input
```
1
15000
```
Expected output
```
15000
```
Example 4
Input
```
1
1
```
Expected output
```
1
```
Example 5
Input
```
5
4 4 4 4 4
```
Expected output
```
20
```