Remove K Bars from a Histogram

Heo Kuang-wang, who took over the class after Lef, plans to set this year's largest-rectangle-in-a-histogram problem again. Heo's histogram is made of $N$ bars placed in order, with heights $H_1, H_2, \cdots, H_N$. All bars have width $1$.

To offer problems of varied difficulty this year, Heo will make a histogram with exactly $K$ bars removed, for each $K=0,1,\cdots,N-1$. Heo likes wide rectangles, so for each $K$ Heo will pick, among all histograms with exactly $K$ bars removed, the one that contains the widest rectangle.

• The largest rectangle contained in a histogram is the rectangle with the greatest area that lies entirely inside the histogram and has sides parallel to the coordinate axes.
• Removing bars means that the remaining bars are joined together in their original order with no gaps.

For example, in a histogram with bar heights $3,1,4,1,5,9$ in order, removing the 2nd and 5th bars leaves bar heights $3,4,1,9$.

Let $f(K)$ be the maximum area of the largest rectangle contained in any histogram obtained by removing exactly $K$ bars from Heo's histogram. Find all $N$ values $f(K)$ for $K=0,1,\cdots,N-1$.

The first line contains $N$, the number of bars in Heo's histogram ($1\leq N\leq 4000$).

The second line contains the heights $H_1, H_2, \ldots, H_N$ of the bars, separated by spaces ($1\leq H_i\leq 10^9$).

Print $N$ lines. On line $i+1$, print $f(i)$ ($0\leq i\leq N-1$).