시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 106 | 48 | 41 | 46.591% |
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.
5 1 7 2 3 9
1 7 7 7 9
5 4 5 3 8 7
4 8 9 12 15