G. Неравные соседние элементы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$, состоящий из $$$n$$$ положительных целых чисел.

Найдите любую перестановку $$$p$$$ чисел $$$[1,2,\dots,n]$$$ такую, что:

  • $$$p_{i-2} < p_i$$$ для всех $$$i$$$, удовлетворяющих $$$3 \leq i \leq n$$$, и
  • $$$a_{p_{i-1}} \neq a_{p_i}$$$ для всех $$$i$$$, удовлетворяющих $$$2 \leq i \leq n$$$.

Или найдите, что таких перестановок не существует.

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

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$) — массив $$$a$$$.

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

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

Для каждого набора входных данных выведите «NO», если не существует подходящей перестановки, иначе выведите «YES» в первой строке, а во второй выведите перестановку $$$p$$$.

Если существует несколько подходящих перестановок, выведите любую из них.

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

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

В первом примере $$$p=[1,2,3]$$$ является единственной перестановкой чисел $$$[1,2,3]$$$, удовлетворяющей данным условиям.

В третьем примере можно показать, что не существует перестановки чисел $$$[1,2,3]$$$, удовлетворяющей данным условиям.