Морти и подпоследовательности

Все знают, как Рик и Морти любят путешествовать и влезать в авантюры! И новое путешествие не исключение! Перед тем как отправиться, Рик попросил Морти помочь ему справиться с одной жизненно-важной задачей, без которой путешествию не состояться. Маленький Морти уже попытался справиться, но у него ничего не вышло, именно поэтому он решил обратиться за помощью к вам!

Задача, которую дал ему Рик звучит следующим образом: дан массив $a$ из $n$ целых положительных чисел. Для всех целых $k$, для которых выполняется неравенство $1 \leq k \leq n$ нужно определить, сколько какое максимальное число элементов можно оставить, убрав некоторые, так, чтобы оставшийся массив можно было разбить на подотрезки, каждый из которых --- возрастающая последовательность, длины не меньше $k$.

Последовательность $a\_{i\_1}, a\_{i\_2}, \dots, a\_{i\_p}$ называется возрастающей подпоследовательностью в массиве $a$, если $a\_{i\_1} \textless a\_{i\_2} \textless \dots \textless a\_{i\_p}$.

Размер последовательности --- количество элементов, которые принадлежат последовательности.

Первая строка входных данных содержит одно целое число $n$ $(1 \leq n \leq 300)$ отвечающее за длину массива. На второй строке содержится массив $a$ из $n$ целых чисел, $1 \leq a\_i \leq 10^9$.

В единственной строке выведите $n$ чисел $b\_i$ --- максимальное число элементов, которые войдут в непересекающиеся возрастающие подотрезки размера не менее $i$ путем исключения некоторого (возможно нулевого) числа элементов из исходного массива.

Рассмотри третий пример. Для $k$ $=$ $1$, ответ равен $5$, так как каждый элемент по отдельности является возрастающей последовательностью. Для $k$ $=$ $2$ максимальный ответ достигается путем избавления, например, от числа 4, разбивая оставшийся массив на два отрезка длины 2, которые являются возрастающими последовательностями. Для $k$ $=$ $3$ максимальный ответ можно достичь удалив элементы со значениями 4 и 3, в результате получив один отрезок, который является возрастающей последовательностью длины 3.