30183번 - 히스토그램 K개 빼기

문제

레프를 이어 수업을 맡게 된 흑왕은 올해도 역시 히스토그램에 포함되는 최대 넓이 직사각형 문제를 내려고 한다. 흑왕이 가진 히스토그램은 기둥 $N$개로 이루어져 있으며, 높이가 $H_1,H_2,\cdots ,H_N$인 기둥들을 순서대로 이어붙여 만들었다. 모든 기둥의 너비는 1ドル$로 동일하다.

올해에는 다양한 난이도의 문제를 제공하기 위해 $K=0,1,\cdots ,N-1$ 각각에 대해 기둥을 $K$개씩 뺀 히스토그램을 가지고 문제를 낼 것이다. 흑왕은 넓이가 넓은 직사각형을 좋아하기 때문에, 각 $K$에 대해 기둥을 정확히 $K$개 뺀 히스토그램 중 가장 넓은 직사각형을 포함할 수 있는 히스토그램을 골라 그것을 가지고 문제를 내려고 한다.

• 어떤 히스토그램에 포함되는 최대 직사각형이란, 해당 히스토그램에 완전히 포함되고 각 변이 좌표축에 평행한 직사각형 중 넓이가 가장 넓은 직사각형이다.
• 히스토그램에서 어떤 기둥(들)을 뺀다는 것은, 빠지지 않고 남은 기둥들을 순서를 유지한 채 빈 틈 없이 이어붙인다는 것이다. 예를 들어, 기둥 높이가 순서대로 3,1,4,1,5,9ドル$인 히스토그램에서 2번째와 5번째 기둥을 뺀다면 남은 히스토그램의 기둥 높이는 3,4,1,9ドル$가 된다.

흑왕이 가진 히스토그램에서 정확히 $K$개의 기둥을 빼서 만들 수 있는 모든 히스토그램들에 대해, 포함되는 최대 직사각형의 넓이의 최댓값을 $f(K)$라고 하자. $K=0,1,\cdots ,N-1$에 대해 총 $N$개의 $f(K)$ 값을 모두 구하자.

입력

첫 번째 줄에 흑왕이 가진 히스토그램을 이루는 기둥의 수 $N$이 주어진다. (1ドル\leq N\leq 4000$)

두 번째 줄에 각 기둥의 높이 $H_1,H_2,...,H_N$이 공백으로 구분되어 주어진다. (1ドル\leq H_i\leq 10^9$)

출력

$N$개의 줄에 걸쳐, $i+1$번째 줄에는 $f(i)$의 값을 출력한다. (0ドル\leq i\leq N-1$)

제한

힌트