Определим $$$f(S)$$$. Пусть у вас есть мультимножество (то есть в нём могут быть повторяющиеся элементы) целых неотрицательных чисел $$$S$$$. За одну операцию вы можете выбрать любое непустое подмножество множества $$$S$$$ (в нём также могут быть повторяющиеся элементы), удалить это подмножество (все входящие в него элементы) из множества $$$S$$$, и добавить в $$$S$$$ MEX удалённого подмножества. Вы можете сделать произвольное число таких операций. После всех операций в $$$S$$$ должно остаться ровно $$$1$$$ число. $$$f(S)$$$ — это наибольшее число, которое могло остаться в $$$S$$$ после любого набора операций.
Вам дан массив целых неотрицательных чисел $$$a$$$ длины $$$n$$$. Для каждого из его $$$n$$$ префиксов посчитайте $$$f(S)$$$, если $$$S$$$ — это этот префикс (для $$$i$$$-го префикса $$$S$$$ это первые $$$i$$$ элементов массива $$$a$$$).
MEX (minimum excluded, минимальное отсутствующее) массива — это наименьшее целое неотрицательное целое число, которое не принадлежит массиву. Например:
Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — размер массива $$$a$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 2 \cdot 10^5$$$) — массив $$$a$$$.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
На каждый набор входных данных выведите $$$n$$$ чисел: $$$f(S)$$$ для каждого из $$$n$$$ префиксов массива $$$a$$$.
48179 57 2 0 2 3 2 31031 0 381 0 1 2 4 3 0 2
179 2 3 3 3 4 4 5 1 1 2 2 1 2 2 3 3 5 5 5
Рассмотрим первой набор входных данных. Для префикса длины $$$1$$$ изначально мультимножество это $$$\{179\}$$$, если ничего не делать, мы получим $$$179$$$.
Для префикса длины $$$2$$$ изначально мультимножество это $$$\{57, 179\}$$$, и используя данную последовательность операций можно получить $$$2$$$:
Рассмотрим второй набор входных данных. Для префикса длины $$$1$$$ изначально мультимножество это $$$\{0\}$$$, если применить к $$$\{0\}$$$ операцию, мы получим мультимножество $$$\{1\}$$$, это и будет ответом.
Название |
---|