Определим оценку последовательности \([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\) удалением нескольких (возможно, нуля или всех) элементов.
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел — стоимости последовательностей \([a_1, a_2, \ldots , a_k]\) в порядке возрастания \(k\).
Примечание
В первом наборе входных данных:
- Максимальная оценка среди подпоследовательностей \([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]\) в этом порядке.