#P1339B. Sorted Adjacent Differences
-
ID: 5312
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Sorted Adjacent Differences
No submission language available for this problem.
Description
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.
Input
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}$).
Output
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.
Samples
2
6
5 -2 4 8 6 5
4
8 1 4 2
5 5 4 6 8 -2
1 2 4 8
Note
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".