D. Shocking Arrangement
constructive algorithms; greedy; math
You are given an array \(a_1, a_2, \ldots, a_n\) consisting of integers such that \(a_1 + a_2 + \ldots + a_n = 0\).You have to rearrange the elements of the array \(a\) so that the following condition is satisfied:$$$\(\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),\)\( where \)|x|\( denotes the absolute value of \)x\(.More formally, determine if there exists a permutation \)p_1, p_2, \ldots, p_n\( that for the array \)a_{p_1}, a_{p_2}, \ldots, a_{p_n}\(, the condition above is satisfied, and find the corresponding array.Recall that the array \)p_1, p_2, \ldots, p_n\( is called a permutation if for each integer \)x\( from \)1\( to \)n\( there is exactly one \)i\( from \)1\( to \)n\( such that \)p_i = x$$$.
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \le t \le 50\,000\)). The description of the test cases follows.The first line of each test case contains a single integer \(n\) (\(1 \le n \le 300\,000\)) — the length of the array \(a\).The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(-10^9 \le a_i \le 10^9\)) — elements of the array \(a\). It is guaranteed that the sum of the array \(a\) is zero, in other words: \(a_1 + a_2 + \ldots + a_n = 0\).It is guaranteed that the sum of \(n\) over all test cases does not exceed \(300\,000\).
For each test case, if it is impossible to rearrange the elements of the array \(a\) in the required way, print ""No"" in a single line.If possible, print ""Yes"" in the first line, and then in a separate line \(n\) numbers — elements \(a_1, a_2, \ldots, a_n\) rearranged in a valid order (\(a_{p_1}, a_{p_2}, \ldots, a_{p_n}\)).If there are several possible answers, you can output any of them.
In the first test case \(\max(a_1, \ldots, a_n) - \min(a_1, \ldots, a_n) = 9\). Therefore, the elements can be rearranged as \([-5, -2, 3, 4]\). It is easy to see that for such an arrangement \(\lvert a_l + \ldots + a_r \rvert\) is always not greater than \(7\), and therefore less than \(9\).In the second test case you can rearrange the elements of the array as \([-3, 2, -3, 2, 2]\). Then the maximum modulus of the sum will be reached on the subarray \([-3, 2, -3]\), and will be equal to \(\lvert -3 + 2 + -3 \rvert = \lvert -4 \rvert = 4\), which is less than \(5\).In the fourth test example, any rearrangement of the array \(a\) will be suitable as an answer, including \([-1, 0, 1]\).