1339B.md (1737B)
1 Source: https://codeforces.com/problemset/problem/1339/B 2 3 B. Sorted Adjacent Differences 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You have array of $n$ numbers $a_{1}, a_{2}, \ldots, a_{n}$. 22 23 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. 24 25 Note that all numbers in $a$ are not necessarily different. In other words, some numbers of $a$ may be same. 26 27 You have to answer independent $t$ test cases. 28 29 Input 30 31 The first line contains a single integer $t$ ($1 \le t \le 10^{4}$) — the number of test cases. 32 33 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}$. 34 35 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}$). 36 37 Output 38 39 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. 40 41 Example 42 43 Input 44 45 ``` 46 2 47 6 48 5 -2 4 8 6 5 49 4 50 8 1 4 2 51 ``` 52 53 Output 54 55 ``` 56 5 5 4 6 8 -2 57 1 2 4 8 58 ``` 59 60 Note 61 62 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". 63 64 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".