Hero's Histogram

Time limit1sMemory limit512 MB

Summary

Given a histogram of n columns, for every prefix of the first j columns report the largest axis-aligned rectangle that fits inside that prefix.

Level: Hard8 of 10
Topics: Stack, Prefix sum, Divide and conquer, Array
Solved: No attempts yet

Problem

Each integer j between 1 and n is assigned a number hj. These numbers are shown as a histogram. We draw the histogram by drawing for each j a column of width 1 and height hj, then lining up all such columns along the x-axis from left to right, starting at the origin.

Examples of histograms corresponding to the sample tests.

Milan has one such histogram and wants to glue onto it a rectangular poster showing his greatest hero, Mr. Malnar.

We say a rectangle is correctly positioned inside the histogram if its vertices have integer coordinates, its sides are parallel to the coordinate axes, and the interior of the rectangle is fully covered by the histogram.

For each number j between 1 and n, find the largest area of a rectangle that can be correctly positioned inside the first j columns of the histogram.

Input

The first line contains the positive integer n (1 ≤ n ≤ 2 · 105), the number of columns in the histogram.

The next line contains n positive integers h1, h2, . . . , hn (1 ≤ hi ≤ 107), the heights of the columns in the histogram.

Output

Print n numbers in a single line. The j-th of these numbers is the largest area of a rectangle that can be correctly positioned inside the first j columns of the histogram.

Examples2

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