I. Лексикографическое разбиение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для данного массива $$$a$$$ определим $$$f(a)$$$ следующим образом:

  • Пусть $$$k$$$ — целое число, такое что $$$1 \leq k \leq n$$$.
  • Разбейте $$$a$$$ на $$$k$$$ подмассивов$$$^{\text{∗}}$$$ $$$s_1,s_2,\ldots,s_k$$$ так, чтобы $$$s_1+s_2+\ldots+s_k=a$$$. Здесь $$$+$$$ обозначает конкатенацию массивов.
  • Пусть $$$b$$$ будет пустым массивом. Для каждого $$$i$$$ от $$$1$$$ до $$$k$$$ по порядку добавьте минимальный элемент $$$s_i$$$ в конец $$$b$$$.
  • По всем возможным $$$k$$$ и разбиениям, $$$f(a)$$$ — это значение $$$k$$$, такое что существует разбиение, которое производит лексикографически наибольший $$$b$$$$$$^{\text{†}}$$$.

Вам даны $$$n$$$ целых чисел $$$x_1,x_2,\ldots,x_n$$$. Определите, существует ли перестановка$$$^{\text{‡}}$$$ $$$a$$$, такая что $$$f([a_1,a_2,\ldots,a_i])=x_i$$$ для каждого $$$1 \leq i \leq n$$$. Если искомая перестановка существует, выведите её. Если есть несколько возможных ответов, вы можете вывести любую.

$$$^{\text{∗}}$$$Массив $$$c$$$ является подмассивом массива $$$d$$$, если $$$c$$$ может быть получен из $$$d$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.

$$$^{\text{†}}$$$Массив $$$c$$$ лексикографически меньше массива $$$d$$$, если и только если выполняется одно из следующего:

  • $$$c$$$ — префикс $$$d$$$, но $$$c \ne d$$$; или
  • в первой позиции, где $$$c$$$ и $$$d$$$ различны, в массиве $$$c$$$ элемент меньше, чем соответствующий элемент в $$$d$$$.

$$$^{\text{‡}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

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

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

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

Следующая строка содержит $$$n$$$ целых чисел $$$x_1,x_2,\ldots,x_n$$$ ($$$1 \leq x_i \leq i$$$) — массив $$$x$$$.

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

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

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

Если ответ положительный, выведите перестановку из $$$n$$$ чисел на следующей строке.

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

В первом наборе входных данных $$$[1,2,3]$$$ является допустимой перестановкой, которая удовлетворяет входному массиву:

  • для $$$[1]$$$ существует только один способ разбиения: один элемент разбиения $$$a[1]$$$, так что $$$f([1])=1$$$.
  • для $$$[1,2]$$$ существует два способа разбиения: один элемент $$$[1,2]$$$ или $$$[1]+[2]$$$. Конструирование $$$b$$$ из первого разбиения дает $$$b=[1]$$$, а конструирование $$$b$$$ из второго разбиения дает $$$b=[1,2]$$$. Второй вариант лексикографически больше, так что $$$f([1,2])=2$$$.
  • Для $$$[1,2,3]$$$ можно показать, что лучшее разбиение — это $$$[1,2]+[3]$$$, что дает $$$b=[1,3]$$$.

Во втором наборе входных данных можно показать, что нет перестановок размера $$$2$$$ с $$$x_1=x_2=1$$$.

В четвертом наборе входных данных одна из перестановок, которая удовлетворяет условиям — это $$$[3,1,2]$$$.