Zig-Zag Array Rearrangement

You are provided with an array of distinct elements, and your task is to rearrange the array elements in a zig-zag manner. Specifically, for every odd index i, the element ARR[i] should be greater than both ARR[i-1] and ARR[i+1].

Input:

The first line contains an integer ‘T’ which represents the number of test cases.
Each test case starts with an integer ‘N’ representing the size of the array.
The next line contains ‘N’ space-separated integers denoting the array elements.

Output:

A zig-zag array for each test case. The output function will validate if the returned array is in zig-zag fashion.

Example:

Input:

N = 4, ARR = [4, 3, 2, 1]

Output:

A possible zig-zag array: [3, 4, 1, 2]

Note:

It is guaranteed that a zig-zag rearrangement is always possible for the given array. Multiple correct answers may exist.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 5*103
• 0 <= ARR[i] <= 106
• Time Limit: 1 sec