| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 5 | 3 | 3 | 60.000% |
Все знают, как Рик и Морти любят путешествовать и влезать в авантюры! И новое путешествие не исключение! Перед тем как отправиться, Рик попросил Морти помочь ему справиться с одной жизненно-важной задачей, без которой путешествию не состояться. Маленький Морти уже попытался справиться, но у него ничего не вышло, именно поэтому он решил обратиться за помощью к вам!
Задача, которую дал ему Рик звучит следующим образом: дан массив $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$ путем исключения некоторого (возможно нулевого) числа элементов из исходного массива.
3 1 2 3
3 3 3
2 1 1
2 0
5 1 4 3 2 9
5 4 3 0 0
Рассмотри третий пример. Для $k$ $=$ 1ドル,ドル ответ равен 5ドル,ドル так как каждый элемент по отдельности является возрастающей последовательностью. Для $k$ $=$ 2ドル$ максимальный ответ достигается путем избавления, например, от числа 4, разбивая оставшийся массив на два отрезка длины 2, которые являются возрастающими последовательностями. Для $k$ $=$ 3ドル$ максимальный ответ можно достичь удалив элементы со значениями 4 и 3, в результате получив один отрезок, который является возрастающей последовательностью длины 3.