def findZigZagSequence(a, n): a.sort() mid = int((n + 1)/2) - 1 #Used as index, so -1 a[mid], a[n-1] = a[n-1], a[mid]

st = mid + 1
ed = n - 2 #The last element is already in place, thus n-2
while(st <= ed):
    a[st], a[ed] = a[ed], a[st]
    st = st + 1
    ed = ed - 1 #Decreasing

for i in range (n):
    if i == n-1:
        print(a[i])
    else:
        print(a[i], end = ' ')
return

test_cases = int(input()) for cs in range (test_cases): n = int(input()) a = list(map(int, input().split())) findZigZagSequence(a, n) Sorting the Array:

The input array a is sorted to ensure it starts in ascending order. This is crucial for constructing the lexicographically smallest zig-zag sequence. Finding and Swapping the Middle Element:

The middle index is calculated as (n + 1) / 2 - 1, adjusted to match Python's 0-based indexing. The middle element is swapped with the last element of the array to start forming the zig-zag pattern. Reversing the Second Half:

From the element right after the middle (st = mid + 1) to the second last element (ed = n - 2), elements are swapped iteratively to reverse this section of the array. This ensures the second half is in decreasing order. Output the Result:

The final zig-zag sequence is printed. The code ensures the last element ends with a newline, while others are separated by spaces. Test Case Loop:

The program handles multiple test cases by iterating over the input and applying the transformation for each array. Key Points: Zig-Zag Definition: The first half of the array is in increasing order, and the second half is in decreasing order. Efficiency: Sorting is O(n log n), and reversing the second half is O(n), making the solution efficient. Lexicographical Order: Sorting ensures the sequence remains lexicographically smallest. This approach ensures the requirements of the problem are met concisely and effectively.