히스토그램 K개 빼기

레프에게서 수업을 넘겨받은 흑왕은 올해도 히스토그램에 포함되는 최대 넓이 직사각형 문제를 내려고 한다. 흑왕의 히스토그램은 높이가 $H_1, H_2, \cdots, H_N$인 기둥 $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, \ldots, H_N$이 공백으로 구분되어 주어진다. ($1\leq H_i\leq 10^9$)

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