Ninja and Alternating Largest Problem Statement

Ninja is given a sequence of numbers and needs to rearrange them so that every second element is greater than its neighbors on both sides.

Example:

Input:

[1, 2, 3, 4, 5]

Output:

[1, 3, 2, 5, 4]

Explanation:

The given array [1, 2, 3, 4, 5] is rearranged to [1, 3, 2, 5, 4] where every second element is greater than its left and right element.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 10^4
• 0 <= array[i] <= 10^5
• Time limit: 1 sec

Input:

The first line of input contains an integer T, the number of test cases.
The first line of each test case contains an integer N, the number of elements in the array.
The second line of each test case contains the array elements.

Output:

For each test case, output 1 if the array can be rearranged to meet the conditions, otherwise output 0.

Note:

If the array returned satisfies the given conditions, the output will be 1; otherwise, it will be 0. Implementation should handle the output internally.