Shuffle Array into Wave Format

Given an array of integers, transform the array into a wave format such that for every consecutive pair, the second element is greater than the first element. In other words, if you denote the resulting array as \(a_0, a_1, a_2, \dots, a_{n-1}\), then for every odd index \(i\) (i.e. \(i=1,3,5,\dots\)), it must hold that:

[ a_i > a_{i-1} ]

The transformation should be performed by comparing each pair of adjacent elements and swapping them if necessary, while only minimally altering the original order.

For example:

• For the input array [9, 4, 17, 3, 19, 5], the output should be [4, 9, 3, 17, 5, 19] because:

• Swap 9 and 4 since 9 > 4.
• Swap 17 and 3 since 17 > 3.
• Swap 19 and 5 since 19 > 5.

This ensures that every odd-indexed element is greater than its immediate predecessor.

inputFormat

The first line of input contains a single integer \(n\) which represents the number of elements in the array. The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single line containing the transformed array with its elements separated by a single space.

## sample

6
9 4 17 3 19 5

4 9 3 17 5 19

</p>