The Stairways of Saharna

Saharna is a beautiful, scenic place in Moldova where, among the caves and waterfalls, one can find stones of many different shapes and sizes. In the Middle Ages these stones were used to build the stairways of fortresses, and as a rule each step of a stairway was made from a single stone.

The stones are heavy, so they lie fixed in a row in a given order. The craftsmen know the height of every stone, so they are given a sequence of integers $H = (h_1, h_2, \dots, h_i, \dots, h_n)$, where $h_i$ is the height of the $i$-th stone.

To build a stairway, a craftsman walks along the row and picks the stones for the steps one after another, keeping their original order. A stone may be chosen only if its height is not lower than the height of the previously chosen stone. In other words, a stairway is a non-decreasing subsequence of $H$ (with the original order preserved).

For example, if $H = (1, 3, 4, 2, 3, 4, 1, 2, 2, 3, 3, 2)$, the underlined stones below form one stairway:

$H = (\underline{1}, 3, 4, \underline{2}, 3, 4, 1, \underline{2}, \underline{2}, \underline{3}, \underline{3}, 2)$

Since bigger is better, to build a finer castle the craftsmen want to use as many stones as possible.

Let $L(H, k)$ be the maximum number of stones that can be used to build $k$ stairways, where the stairways use disjoint stones and each stairway has at least one step.

For the example above, $L(H, 1) = 6$: the underlined stones form an optimal single stairway.

Likewise, $L(H, 2) = 9$. In the picture below the stones of the first stairway are marked with a single underline ($\underline{\ }$) and the stones of the second with a double underline ($\underline{\underline{\ }}$):

$H = (\underline{1}, \underline{\underline{3}}, \underline{\underline{4}}, \underline{2}, 3, \underline{\underline{4}}, 1, \underline{2}, \underline{2}, \underline{3}, \underline{3}, 2)$

For $k = 2$ the first stairway uses 6 stones and the second uses 3.

If we want three stairways, the maximum number of stones that can be used is shown below:

$H = (\underline{1}, \underline{\underline{\underline{3}}}, \underline{\underline{\underline{4}}}, \underline{2}, \underline{3}, \underline{\underline{\underline{4}}}, \underline{\underline{1}}, \underline{\underline{2}}, \underline{\underline{2}}, \underline{3}, \underline{3}, \underline{\underline{2}})$

The triple underline marks the third stairway; the other marks keep their previous meaning. Hence $L(H, 3) = 12$. For $k = 3$ the first stairway uses 5 stones, the second 4, and the third 3. Note that the first and second stairways chosen for $k = 3$ may differ from those chosen for $k = 1$ and $k = 2$.

As $k$ takes the values $1, 2, 3, \dots$, at some point, for some number $q$, we get $L(H, q) = n$, where $n$ is the total number of stones.

Given the sequence of heights $H$, write a program that computes $L(H, k)$ for every $k = 1, 2, \dots, q$.

The first line contains a positive integer $n$. The second line contains $n$ positive integers $h_1, h_2, \dots, h_n$, separated by spaces.

Print $q$ lines. The $k$-th line must contain $L(H, k)$ for $k = 1, 2, \dots, q$, where $q$ is the smallest value with $L(H, q) = n$.

• $1 \le n \le 5000$
• $1 \le h_i \le 255,\ i = 1, 2, \dots, n$