히어로의 히스토그램
시간 제한1초메모리 제한512 MB
히스토그램의 기둥 n개가 주어질 때, 각 접두사 1번부터 j번 기둥 안에 들어가는 축에 평행한 직사각형의 최대 넓이를 모두 구한다.
문제
1과 n 사이의 각 정수 j에는 수 hj가 대응된다. 이 수들을 히스토그램으로 나타낸다. 히스토그램은 각 j에 대해 너비 1, 높이 hj인 막대를 그린 뒤, 그런 막대를 모두 원점에서 시작해 x축을 따라 왼쪽에서 오른쪽으로 나란히 배치하여 그린다.
예제 입력에 대응하는 히스토그램의 예.
Milan은 이런 히스토그램 하나를 가지고, 그 위에 자신의 가장 위대한 영웅인 Malnar 씨가 그려진 직사각형 포스터를 붙이려 한다.
직사각형이 히스토그램 안에 올바르게 놓였다고 말하려면, 직사각형의 꼭짓점 좌표가 정수이고, 변이 좌표축과 평행하며, 직사각형의 내부가 히스토그램으로 완전히 덮여 있어야 한다.
1과 n 사이의 각 j에 대해, 히스토그램의 처음 j개 열 안에 올바르게 놓을 수 있는 직사각형의 최대 넓이를 구하라.
입력
첫째 줄에는 히스토그램의 열 개수를 나타내는 자연수 n (1 ≤ n ≤ 2 · 105)이 주어진다.
다음 줄에는 히스토그램에서 열의 높이를 나타내는 n개의 자연수 h1, h2, . . . , hn (1 ≤ hi ≤ 107)이 주어진다.
출력
한 줄에 n개의 수를 출력한다. 그중 j번째 수는 히스토그램의 처음 j개 열 안에 올바르게 놓을 수 있는 직사각형의 최대 넓이이다.