B. Sorted Adjacent Differences
constructive algorithms; sortings
You have array of \(n\) numbers \(a_{1}, a_{2}, \ldots, a_{n}\). Rearrange these numbers to satisfy \(|a_{1} - a_{2}| \le |a_{2} - a_{3}| \le \ldots \le |a_{n-1} - a_{n}|\), where \(|x|\) denotes absolute value of \(x\). It's always possible to find such rearrangement.Note that all numbers in \(a\) are not necessarily different. In other words, some numbers of \(a\) may be same.You have to answer independent \(t\) test cases.
The first line contains a single integer \(t\) (\(1 \le t \le 10^{4}\)) — the number of test cases.The first line of each test case contains single integer \(n\) (\(3 \le n \le 10^{5}\)) — the length of array \(a\). It is guaranteed that the sum of values of \(n\) over all test cases in the input does not exceed \(10^{5}\).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}\)).
For each test case, print the rearranged version of array \(a\) which satisfies given condition. If there are multiple valid rearrangements, print any of them.
In the first test case, after given rearrangement, \(|a_{1} - a_{2}| = 0 \le |a_{2} - a_{3}| = 1 \le |a_{3} - a_{4}| = 2 \le |a_{4} - a_{5}| = 2 \le |a_{5} - a_{6}| = 10\). There are other possible answers like ""5 4 5 6 -2 8"".In the second test case, after given rearrangement, \(|a_{1} - a_{2}| = 1 \le |a_{2} - a_{3}| = 2 \le |a_{3} - a_{4}| = 4\). There are other possible answers like ""2 4 8 1"".