Rearrange Array for Zigzag Pattern

Given an array of integers, rearrange the array such that every element at an odd index is greater than its adjacent neighbors. In other words, for every odd index \( i \) (where \( i \ge 1 \)), the condition \( a[i] > a[i-1] \) and, if \( i+1 a[i+1] \) must hold. One effective strategy is to first sort the array, then assign the smallest half of the elements to the even positions and the largest half (in reverse order) to the odd positions. This approach guarantees a valid zigzag arrangement.

inputFormat

The input begins with an integer \( T \) representing the number of test cases. Each test case consists of two lines. The first line contains an integer \( N \) which denotes the number of elements in the array. The second line contains \( N \) space-separated integers representing the array elements.

outputFormat

For each test case, output a single line containing the rearranged array. The elements must be separated by a single space and arranged so that every odd-indexed element (using 0-based indexing) is greater than its adjacent neighbors.

2
6
1 3 4 2 5 6
5
9 7 4 2 1

1 6 2 5 3 4
1 9 2 7 4