Histogram and Blue Rectangles

Time limit2sMemory limit512 MB

Summary

For each prefix of j columns of a histogram with heights a_i, find the largest axis-aligned rectangle whose interior lies entirely within those columns.

Level: Hard9 of 10
Topics: Stack, Dynamic programming, Geometry
Solved: No attempts yet

Problem

Consider an integer array $a$ of length $n$ where all $a_i$ are positive. Such an array may be represented as a histogram. To draw the histogram, for each $i$ from 0 to $n-1$ , draw a blue rectangle with vertices $(i,0)$ , $(i,a_i)$ , $(i+1,a_i)$ , $(i+1,0)$ .

A rectangle with vertices at integer points is called covered by the histogram if its sides are parallel to the coordinate axes and all the internal points of the rectangle are blue.

For each $j$ between 1 and $n$ , calculate the maximal area of the rectangle covered by the first $j$ columns of the given histogram.

Input

The first line contains one integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ), the length of the array $a$ . The second line contains $n$ integers, where the $i$ -th integer is $a_i$ ( $1 \le a_i \le 10^7$ ).

Output

Print $n$ integers, each on a new line. The $i$ -th integer is the maximal area of the rectangle covered by the first $i$ columns of the given histogram.

Examples2

Example 1
Input
```
5
1 7 2 3 9
```
Expected output
```
1
7
7
7
9
```
Example 2
Input
```
5
4 5 3 8 7
```
Expected output
```
4
8
9
12
15
```