Магнус только что узнал о MEX, и он ему так понравился, что он решил сразу его использовать.
Учитывая массив \(a\) из \(n\) неотрицательных целых чисел, Магнус хочет создать новый массив \(b\), который сформирован следующим образом:
Пока массив \(a\) не пуст:
- Выберите целое число \(k\) (\(1 \leq k \leq |a|\)).
- Добавьте MEX первых \(k\) чисел массива \(a\) в конец массива \(b\) и удалите эти числа из массива \(a\), сдвинув позиции оставшихся чисел в \(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\).
Выходные данные
Для каждого тестового примера выведите \(m\) — длину лексикографически максимального массива \(b\), который может создать Магнус, за которым следуют \(m\) целых чисел, обозначающие элементы массива \(b\).
Примечание
В первом наборе входных данных лексикографически максимальный массив \(b\) получается выбором \(k=5\), что приводит к \(MEX\) всего массива \(a\). Он лексикографически максимален, так как массив, начинающийся с меньшего числа, чем \(4\), лексикографически меньше, и выбор \(k<5\) приведет к массиву, начинающемуся с числа меньше чем \(4\).
Во втором наборе входных данных есть два способа получить максимальный массив: сначала выбрать \(k=6\), затем \(k=2\) или сначала выбрать \(k=7\), а затем \(k=1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5
1 0 2 0 3
8
2 2 3 4 0 1 2 0
1
1
5
0 1 2 3 4
4
0 1 1 0
10
0 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
|