C. Оценка подпоследовательностей
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Определим оценку последовательности $$$[s_1, s_2, \ldots, s_d]$$$ как $$$\displaystyle \frac{s_1\cdot s_2\cdot \ldots \cdot s_d}{d!}$$$, где $$$d!=1\cdot 2\cdot \ldots \cdot d$$$. В частности, оценка пустой последовательности равна $$$1$$$.

Для последовательности $$$[s_1, s_2, \ldots, s_d]$$$ пусть $$$m$$$ будет максимальной оценкой среди всех ее подпоследовательностей. Тогда ее стоимость определяется как максимальная длина подпоследовательности с оценкой $$$m$$$.

Вам дана неубывающая последовательность $$$[a_1, a_2, \ldots, a_n]$$$ целых чисел длины $$$n$$$. Другими словами, выполняется условие $$$a_1 \leq a_2 \leq \ldots \leq a_n$$$. Для каждого $$$k=1, 2, \ldots , n$$$ найдите стоимость последовательности $$$[a_1, a_2, \ldots , a_k]$$$.

Последовательность $$$x$$$ называется подпоследовательностью последовательности $$$y$$$, если $$$x$$$ получается из $$$y$$$ удалением нескольких (возможно, нуля или всех) элементов.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1\le n\le 10^5$$$) — длину заданной последовательности.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\leq n$$$) — заданную последовательность. Гарантируется, что ее элементы расположены в неубывающем порядке.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел — стоимости последовательностей $$$[a_1, a_2, \ldots , a_k]$$$ в порядке возрастания $$$k$$$.

Пример
Входные данные
3
3
1 2 3
2
1 1
5
5 5 5 5 5
Выходные данные
1 1 2 
1 1 
1 2 3 4 5
Примечание

В первом наборе входных данных:

  • Максимальная оценка среди подпоследовательностей $$$[1]$$$ равна $$$1$$$. Подпоследовательности $$$[1]$$$ и $$$[]$$$ (пустая последовательность) — единственные с такой оценкой. Таким образом, стоимость $$$[1]$$$ составляет $$$1$$$.
  • Максимальная оценка среди подпоследовательностей $$$[1, 2]$$$ равна $$$2$$$. Единственная подпоследовательность с такой оценкой — $$$[2]$$$. Таким образом, стоимость $$$[1, 2]$$$ составляет $$$1$$$.
  • Максимальная оценка среди подпоследовательностей $$$[1, 2, 3]$$$ равна $$$3$$$. Подпоследовательности $$$[2, 3]$$$ и $$$[3]$$$ — единственные с такой оценкой. Таким образом, стоимость $$$[1, 2, 3]$$$ составляет $$$2$$$.
Следовательно, ответ в этом случае равен $$$1\:\:1\:\:2$$$ — стоимости $$$[1], [1, 2]$$$ и $$$[1, 2, 3]$$$ в этом порядке.