Wave Sort

Problem Statement: Given an array of integers, rearrange the array into a wave-like form such that for every odd index \(i\) (with \(i\) starting from 0), the element \(a[i]\) is less than or equal to its adjacent elements. In other words, the array must satisfy \(a[i] \leq a[i-1]\) and, if applicable, \(a[i] \leq a[i+1]\) for every odd index \(i\). Output one valid arrangement that meets these conditions.

Note: The solution should read input from stdin and write the output to stdout.

inputFormat

The first line 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

Print a single line containing the elements of the wave sorted array, separated by spaces.

6
3 6 5 10 7 20

6 3 10 5 20 7