You are given an unsorted array of integers, write a program to sort it in wave form.

Problem Note:

  • The array elements in the resultant array must be such that A[0] >= A[1] <= A[2] >= A[3] <= A[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: A = [5, 2, 9, 3, 2]
Output: [2,2,5,3,9]

Example 2

Input: A = [3,2,9,6,4,1]
Output: [2,1,4,3,9,6]

Example 3

Input: A = [4,2,9,1,21,43,24]
Output: [2,1,9,4,24,21,43]