Codeforces Round 794 (Div. 1) |
---|
Закончено |
Вам дано $$$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$$$ выполняется хотя бы одно из следующих условий:
Чтобы выражения выше имели смысл для $$$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$$$ и удовлетворяют условиям из утверждения.
431 1 241 9 8 442 0 2 261 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$$$, меньше своих соседей, а остальные элементы больше.
Название |
---|