시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 14 13 12 100.000%

문제

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

The rectangle with the vertices at integer points is called \emph{covered} by the histogram, if the 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 first $j$ columns of the given histogram.

입력

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

출력

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

예제 입력 1

5
1 7 2 3 9


예제 출력 1

1
7
7
7
9


예제 입력 2

5
4 5 3 8 7


예제 출력 2

4
8
9
12
15