Permutation to Maximize Sum of Extremes in Subarrays of Length 3

You are given an array of n integers. Your task is to find a permutation of the array that maximizes the sum of the minimum and maximum elements in every contiguous subarray of length 3.

More formally, given a permutation P of the array A = [a₁, a₂, ..., a_n], for every contiguous subarray of length 3, i.e. [P[i], P[i+1], P[i+2]] for 1 ≤ i ≤ n-2, you need to maximize the following sum:

\( S = \sum_{i=1}^{n-2} (\min(P[i],P[i+1],P[i+2]) + \max(P[i],P[i+1],P[i+2])) \)

Note: If n = 3, then the only permutation possible is the array itself.

Hint: A greedy approach based on sorting the array and then choosing elements alternately from the beginning and end of the sorted array can achieve the desired permutation.

inputFormat

The input is given via standard input (stdin) and has the following format:

T
n1
a1 a2 ... an₁
n2
a1 a2 ... an₂
...
nT
a1 a2 ... anₜ

Here, T is the number of test cases. For each test case, the first line contains the integer n (the size of the array), and the second line contains n space-separated integers.

All input is read from standard input.

outputFormat

For each test case, output a single line containing the permutation of the array that optimizes the objective. The order of the numbers should be space-separated. All output should be written to standard output (stdout).

## sample

2
3
3 1 2
4
1 4 3 2

3 1 2
4 1 3 2

</p>