Все знают, как Рик и Морти любят путешествовать и влезать в авантюры! И новое путешествие не исключение! Перед тем как отправиться, Рик попросил Морти помочь ему справиться с одной жизненно-важной задачей, без которой путешествию не состояться. Маленький Морти уже попытался справиться, но у него ничего не вышло, именно поэтому он решил обратиться за помощью к вам!
Задача, которую дал ему Рик звучит следующим образом: дан массив a из n целых положительных чисел. Для всех целых k, для которых выполняется неравенство 1 ≤ k ≤ n нужно определить, сколько какое максимальное число элементов можно оставить, убрав некоторые, так, чтобы оставшийся массив можно было разбить на подотрезки, каждый из которых — возрастающая последовательность, длины не меньше k.
Последовательность ai1, ai2, ..., aip называется возрастающей подпоследовательностью в массиве a, если .
Размер последовательности — количество элементов, которые принадлежат последовательности.
Первая строка входных данных содержит одно целое число n (1 ≤ n ≤ 300) отвечающее за длину массива. На второй строке содержится массив a из n целых чисел, 1 ≤ ai ≤ 109.
В единственной строке выведите n чисел bi — максимальное число элементов, которые войдут в непересекающиеся возрастающие подотрезки размера не менее 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.