Вам дан массив \(a_1, a_2, \ldots, a_n\), состоящий из целых чисел, такой что \(a_1 + a_2 + \ldots + a_n = 0\).
Переставьте элементы массива \(a\) таким образом, чтобы выполнялось следующее условие:
\(\)\max\limits_{1 \le l \le r \le n} \lvert a_l + a_{l+1} + \ldots + a_r \rvert < \max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n),\(\) где \(|x|\) обозначает модуль числа \(x\).
Более формально, вам нужно выяснить, существует ли такая перестановка \(p_1, p_2, \ldots, p_n\), что для массива \(a_{p_1}, a_{p_2}, \ldots, a_{p_n}\) выполняется условие выше, и найти полученный массив.
Напомним, что массив \(p_1, p_2, \ldots, p_n\) называется перестановкой, если для каждого числа \(x\) от \(1\) до \(n\) существует ровно одно \(i\) от \(1\) до \(n\) такое, что \(p_i = x\).
Выходные данные
Для каждого набора входных данных, если переставить элементы массива \(a\) требуемым образом невозможно, в единственной строке выведите «No».
Если же это возможно, в первой строке выведите «Yes», а далее в отдельной строке \(n\) чисел — элементы \(a_1, a_2, \ldots, a_n\), переставленные в нужном порядке (\(a_{p_1}, a_{p_2}, \ldots, a_{p_n}\)).
Если возможных ответов несколько, вы можете вывести любой из них.
Примечание
В первом наборе входных данных \(\max(a_1, \ldots, a_n) - \min(a_1, \ldots, a_n) = 9\). Поэтому элементы можно переставить следующим образом: \([-5, -2, 3, 4]\). Несложно видеть, что для такой расстановки значение \(\lvert a_l + \ldots + a_r \rvert\) всегда не больше \(7\), а значит и меньше \(9\).
Во втором наборе входных данных можно переставить элементы массива следующим образом: \([-3, 2, -3, 2, 2]\). Тогда максимальный модуль суммы будет достигаться на подмассиве \([-3, 2, -3]\), и будет равен \(\lvert -3 + 2 + -3 \rvert = \lvert -4 \rvert = 4\), что меньше чем \(5\).
В четвёртом тестовом примере любая перестановка массива \(a\) подойдёт в качестве ответа, в том числе и \([-1, 0, 1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
4
3 4 -2 -5
5
2 2 2 -3 -3
8
-3 -3 1 1 1 1 1 1
3
0 1 -1
7
-3 4 3 4 -4 -4 0
1
0
7
-18 13 -18 -17 12 15 13
|
Yes
-5 -2 3 4
Yes
-3 2 -3 2 2
Yes
1 1 1 -3 1 1 1 -3
Yes
-1 0 1
Yes
4 -4 4 -4 0 3 -3
No
Yes
13 12 -18 15 -18 13 -17
|