Rearrange Array for Alternating High-Low

Given an array of integers, rearrange the elements of the array such that they are in alternating high-low order. In other words, for each pair of adjacent elements, arr[i] should be less than arr[i+1] if i is even, and greater if i is odd. Input format: - The first line contains an integer n (1 <= n <= 10^5), the number of elements in the array. - The second line contains n space-separated integers (|a[i]| <= 1000), the elements of the array. Output format: - Output a single line of the rearranged array as space-separated integers. Example: Input: 5 1 2 3 4 5 Output: 1 3 2 5 4