Codeforces Round 767 (Div. 1) |
---|
Закончено |
Магнус только что узнал о MEX, и он ему так понравился, что он решил сразу его использовать.
Учитывая массив $$$a$$$ из $$$n$$$ неотрицательных целых чисел, Магнус хочет создать новый массив $$$b$$$, который сформирован следующим образом:
Пока массив $$$a$$$ не пуст:
Магнус любит большие массивы так же сильно, как и MEX, поэтому он хочет, чтобы новый массив $$$b$$$ был лексикографически максимальным. Магнус просит вас сказать ему, какой лексикографически максимальный массив $$$b$$$, он может создать, построив его оптимальным образом.
Массив $$$x$$$ лексикографически больше массива $$$y$$$, если в первой позиции, где $$$x$$$ и $$$y$$$ различаются $$$x_i > y_i$$$, или если $$$|x| > |y|$$$ и $$$y$$$ — это префикс $$$x$$$ (где $$$|x|$$$ обозначает размер массива $$$x$$$).
MEX набора неотрицательных целых чисел — это минимальное неотрицательное целое число, которого нет в наборе. Например, MEX ({$$${1, 2, 3}$$$}) $$$= 0$$$ и MEX ({$$${0, 1, 2, 4, 5}$$$}) $$$= 3$$$.
Первая строка входных данных содержит единственное целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество тестов. Описание тестовых примеров следует ниже.
Первая строка каждого тестового примера содержит единственное целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — количество элементов в массиве $$$a$$$.
Вторая строка каждого тестового примера содержит $$$n$$$ неотрицательных целых чисел $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i \leq n$$$), где $$$a_i$$$ — это $$$i$$$-е число из массива $$$a$$$.
Гарантируется, что сумма $$$n$$$ по всем тестам не превосходит $$$2 \cdot 10^5$$$.
Для каждого тестового примера выведите $$$m$$$ — длину лексикографически максимального массива $$$b$$$, который может создать Магнус, за которым следуют $$$m$$$ целых чисел, обозначающие элементы массива $$$b$$$.
651 0 2 0 382 2 3 4 0 1 2 01150 1 2 3 440 1 1 0100 0 2 1 1 1 0 0 1 1
1 4 2 5 1 1 0 1 5 2 2 2 4 3 2 2 0
В первом наборе входных данных лексикографически максимальный массив $$$b$$$ получается выбором $$$k=5$$$, что приводит к $$$MEX$$$ всего массива $$$a$$$. Он лексикографически максимален, так как массив, начинающийся с меньшего числа, чем $$$4$$$, лексикографически меньше, и выбор $$$k<5$$$ приведет к массиву, начинающемуся с числа меньше чем $$$4$$$.
Во втором наборе входных данных есть два способа получить максимальный массив: сначала выбрать $$$k=6$$$, затем $$$k=2$$$ или сначала выбрать $$$k=7$$$, а затем $$$k=1$$$.
Название |
---|