Maximizing Minimum Difference Rearrangement

Given an integer array, your task is to rearrange its elements to maximize the minimum difference between consecutive elements. To achieve this, sort the array and then alternately select the smallest and largest remaining elements until all elements are used.

For example, consider the array [1, 5, 9, 3]. After sorting, it becomes [1, 3, 5, 9]. Rearranging it by alternately picking elements from the beginning and the end of the sorted array will yield [1, 9, 3, 5].

inputFormat

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

outputFormat

For each test case, output a single line containing the rearranged array with its elements separated by spaces. The order of elements should be determined by first selecting the smallest element, then the largest, then the next smallest, then the next largest, and so on.## sample

2
4
1 5 9 3
5
10 1 7 4 2

1 9 3 5
1 10 2 7 4