Определим \(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, минимальное отсутствующее) массива — это наименьшее целое неотрицательное целое число, которое не принадлежит массиву. Например:
- MEX массива \([2,2,1]\) равен \(0\), потому что \(0\) не принадлежит массиву.
- MEX массива \([3,1,0,1]\) равен \(2\), потому что \(0\) и \(1\) принадлежат массиву, а \(2\) — нет.
- MEX массива \([0,3,1,2]\) равен \(4\), потому что \(0\), \(1\), \(2\) и \(3\) принадлежат массиву, а \(4\) — нет.
Выходные данные
На каждый набор входных данных выведите \(n\) чисел: \(f(S)\) для каждого из \(n\) префиксов массива \(a\).
Примечание
Рассмотрим первой набор входных данных. Для префикса длины \(1\) изначально мультимножество это \(\{179\}\), если ничего не делать, мы получим \(179\).
Для префикса длины \(2\) изначально мультимножество это \(\{57, 179\}\), и используя данную последовательность операций можно получить \(2\):
- применить операцию к \(\{57\}\), мультимножество после этого — \(\{0, 179\}\).
- применить операцию к \(\{179\}\), мультимножество после этого — \(\{0, 0\}\).
- применить операцию к \(\{0\}\), мультимножество после этого — \(\{0, 1\}\).
- применить операцию к \(\{0, 1\}\), мультимножество после этого — \(\{2\}\), это и есть наш ответ.
Рассмотрим второй набор входных данных. Для префикса длины \(1\) изначально мультимножество это \(\{0\}\), если применить к \(\{0\}\) операцию, мы получим мультимножество \(\{1\}\), это и будет ответом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
8
179 57 2 0 2 3 2 3
1
0
3
1 0 3
8
1 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
|