Вам дан массив из \(n\) целых чисел от \(0\) до \(n\) включительно.
За одну операцию вы можете выбрать любой элемент массива и заменить его на MEX всех элементов массива (этот MEX может измениться после операции).
Например, если текущий массив равен \([0, 2, 2, 1, 4]\), то вы можете выбрать второй элемент и заменить его на MEX существующих элементов — \(3\). Массив станет равным \([0, 3, 2, 1, 4]\).
Вы должны сделать массив неубывающим, используя не более \(2n\) операций.
Можно показать, что это всегда возможно. Обратите внимание, что вы не должны минимизировать количество операций. Если есть много решений, вы можете найти любое из них.
–
Напомним, что массив \(b[1 \ldots n]\) является неубывающим тогда и только тогда, когда \(b_1 \le b_2 \le \ldots \le b_n\).
Напомним, что MEX массива равен наименьшему неотрицательному целому числу, которое не принадлежит массиву. Например:
- 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\) — нет.
Стоит отметить, что MEX массива длины \(n\) всегда находится между \(0\) и \(n\) включительно.
Выходные данные
Для каждого набора входных данных вы должны вывести две строки:
Первая строка должна содержать одно целое число \(k\) (\(0 \le k \le 2n\)) — количество операций, которые вы выполняете.
Вторая строка должна содержать \(k\) целых чисел \(x_1, \ldots, x_k\) (\(1 \le x_i \le n\)), где \(x_i\) — индекс элемента, с котором вы выполняете операцию \(i\).
Если есть много решений, вы можете найти любое из них. Пожалуйста, помните, что минимизировать \(k\) не требуется.
Примечание
В первом наборе входных данных массив уже не убывает (\(2 \le 2 \le 3\)).
Объяснение второго набора входных данных (элемент, изменяемый каждой операцией, окрашен красным):
- \(a = [2, 1, 0]\) ; начальный MEX равен \(3\).
- \(a = [2, 1, \color{red}{3}]\) ; новый MEX равен \(0\).
- \(a = [\color{red}{0}, 1, 3]\) ; новый MEX равен \(2\).
- Итоговый массив неубывающий: \(0 \le 1 \le 3\).
Объяснение третьего набора входных данных:
- \(a = [0, 7, 3, 1, 3, 7, 7]\) ; начальный MEX равен \(2\).
- \(a = [0, \color{red}{2}, 3, 1, 3, 7, 7]\) ; новый MEX равен \(4\).
- \(a = [0, 2, 3, 1, \color{red}{4}, 7, 7]\) ; новый MEX равен \(5\).
- \(a = [0, 2, 3, 1, \color{red}{5}, 7, 7]\) ; новый MEX равен \(4\).
- \(a = [0, 2, 3, \color{red}{4}, 5, 7, 7]\) ; новый MEX равен \(1\).
- Итоговый массив неубывающий: \(0 \le 2 \le 3 \le 4 \le 5 \le 7 \le 7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
2 2 3
3
2 1 0
7
0 7 3 1 3 7 7
9
2 0 1 1 2 4 4 2 0
9
8 4 7 6 1 2 3 0 5
|
0
2
3 1
4
2 5 5 4
11
3 8 9 7 8 5 9 6 4 1 2
10
1 8 1 9 5 2 4 6 3 7
|