C. Циклический локальный минимакс
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$. Можно ли расположить их на окружности так, чтобы каждое число было строго больше обоих своих соседей или строго меньше обоих своих соседей?

Другими словами, определите, существует ли перестановка $$$b_1, b_2, \ldots, b_n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ такая, что для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ выполняется хотя бы одно из следующих условий:

  • $$$b_{i-1} < b_i > b_{i+1}$$$.
  • $$$b_{i-1} > b_i < b_{i+1}$$$

Чтобы выражения выше имели смысл для $$$i=1$$$ и $$$i=n$$$, мы определяем $$$b_0=b_n$$$ и $$$b_{n+1}=b_1$$$.

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

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

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

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

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.

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

Для каждого набора входных данных, если невозможно расположить числа на окружности таким образом, выведите $$$\texttt{NO}$$$.

В противном случае выведите $$$\texttt{YES}$$$. Во второй строке выведите $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$, которые являются перестановкой $$$a_1, a_2, \ldots, a_n$$$ и удовлетворяют условиям из утверждения.

Пример
Входные данные
4
3
1 1 2
4
1 9 8 4
4
2 0 2 2
6
1 1 1 11 111 1111
Выходные данные
NO
YES
1 8 4 9 
NO
YES
1 11 1 111 1 1111
Примечание

Можно показать, что для первого и третьего наборов входных данных такой расстановки не существует.

Во втором наборе входных данных подходит расстановка $$$[1, 8, 4, 9]$$$, в которой $$$1$$$ и $$$4$$$ меньше своих соседей, а $$$8, 9$$$ больше.

В четвертом наборе входных данных работает расстановка $$$[1, 11, 1, 111, 1, 1111]$$$, в которой три элемента, равные $$$1$$$, меньше своих соседей, а остальные элементы больше.