Вам дано \(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\).
Выходные данные
Для каждого набора входных данных, если невозможно расположить числа на окружности таким образом, выведите \(\texttt{NO}\).
В противном случае выведите \(\texttt{YES}\). Во второй строке выведите \(n\) целых чисел \(b_1, b_2, \ldots, b_n\), которые являются перестановкой \(a_1, a_2, \ldots, a_n\) и удовлетворяют условиям из утверждения.
Примечание
Можно показать, что для первого и третьего наборов входных данных такой расстановки не существует.
Во втором наборе входных данных подходит расстановка \([1, 8, 4, 9]\), в которой \(1\) и \(4\) меньше своих соседей, а \(8, 9\) больше.
В четвертом наборе входных данных работает расстановка \([1, 11, 1, 111, 1, 1111]\), в которой три элемента, равные \(1\), меньше своих соседей, а остальные элементы больше.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|