E1. N-MEX (Конструктивная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Карта клановой войны — Supercell, Clash of Clans

Это конструктивная версия задачи. Отличие между версиями заключается в том, что в этой версии вам нужно либо построить ответ, либо сообщить, что это невозможно, и $$$0 \leq b_i \leq 10^9$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Мастер-строитель не любит повторяющиеся задачи — ремонт базы, улучшение ратуши пятнадцать раз и решение еще большего количества задач по MEX. Поэтому это не будет вашей обычной задачей по MEX.

Для любого положительного целого числа $$$k$$$ определим $$$k$$$-mex коллекции целых чисел $$$S$$$ как $$$k$$$-е по величине неотрицательное целое число, отсутствующее в $$$S$$$. Например, $$$1$$$-mex и $$$2$$$-mex для $$$[1, 2, 1]$$$ равны $$$0$$$ и $$$3$$$ соответственно.

Пусть $$$n$$$ будет положительным целым числом, и рассмотрим массив неотрицательных целых чисел $$$[a_1, \ldots, a_n]$$$. Определите, существует ли массив неотрицательных целых чисел $$$[b_1, \ldots, b_n]$$$, такой что:

  • Для всех $$$1 \leq i \leq n$$$, $$$(n-i+1)$$$-mex массива $$$[b_1, \ldots, b_i]$$$ равен $$$a_i$$$.
Кроме того, если такой массив $$$b$$$ существует, выведите любой такой $$$[b_1, \ldots, b_n]$$$.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — длина массива $$$a$$$.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора выведите строку, содержащую либо «YES», либо «NO», которая показывает существует ли массив $$$b$$$. Вы можете выводить ответ в любом регистре (верхнем или нижнем). Например, строки «yEs», «yes», «Yes», и «YES» будут распознаны как положительные ответы.

Затем, если вы ответили «YES», выведите вторую строку, содержащую $$$n$$$ целых чисел $$$b_1, \ldots, b_n$$$ ($$$0 \leq b_i \leq 10^9$$$) так, чтобы для всех $$$1 \leq i \leq n$$$, $$$(n-i+1)$$$-mex массива $$$[b_1, \ldots, b_i]$$$ равен $$$a_i$$$.

Пример
Входные данные
6
3
3 3 1
3
2 1 3
1
0
1
2
4
7 5 2 2
6
6 6 6 4 3 3
Выходные данные
YES
2 0 2 
NO
YES
67 
NO
NO
YES
5 2 1 5 2 0
Примечание

В первом наборе массив $$$a = [3, 3, 1]$$$. Мы можем проверить, что массив $$$b = [2, 0, 2]$$$ удовлетворяет условиям, потому что:

  • $$$3$$$-mex массива $$$[b_1] = [2]$$$ равен $$$a_1 = 3$$$,
  • $$$2$$$-mex массива $$$[b_1, b_2] = [2, 0]$$$ равен $$$a_2 = 3$$$,
  • $$$1$$$-mex массива $$$[b_1, b_2, b_3] = [2, 0, 2]$$$ равен $$$a_3 = 1$$$.

Во втором наборе массив $$$a = [2, 1, 3]$$$. Можно показать, что подходящего массива $$$b$$$ не существует.

В третьем наборе массив $$$a = [0]$$$. Мы можем проверить, что массив $$$b = [67]$$$ удовлетворяет условиям, потому что $$$1$$$-mex массива $$$[b_1] = [67]$$$ равен $$$a_1 = 0$$$.