You are given an unsorted array of integers(arr) of length n, write a program to sort it in wave form.

Problem Note:

• The array elements in the resultant array must be such that arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] .....
• If there are multiple sorted orders in wave form, return the one which is lexicographically smallest.
• The array may contain duplicates.

Example 1

Input: arr = [5, 2, 9, 3, 2]
Output: [2, 2, 5, 3, 9]
Explanation: In the above example, you can see 2 >= 2 <= 5 >= 3 <= 9. Thus we get, arr = [2, 2, 5, 3, 9] as output which is sorted in wave form.

Example 2

Input: arr = [3, 2, 9, 6, 4, 1]
Output: [2, 1, 4, 3, 9, 6]
Explanation: In the above example, you can see 2 >= 1 <= 4 >= 3 <= 9 >= 6. Thus we get, arr = [2, 1, 4, 3, 9, 6] as output which is sorted in wave form.

Example 3

Input: arr = [4, 2, 9, 1, 21, 43, 24]
Output: [2, 1, 9, 4, 24, 21, 43]
Explanation: In the above example, you can see 2 >= 1 <= 9 >= 4 <= 24 >= 21 <= 43. Thus we get, arr = [2, 1, 9, 4, 24, 21, 43] as output which is sorted in wave form.