Wave Arrangement of Student Heights

You are given an array of N integers representing the heights of students standing in a line. Your task is to rearrange the array so that every student (except the first and last) is either strictly taller than both of its neighbors or strictly shorter than both. More formally, for every index i (1 ≤ i ≤ N-2), the following condition must hold:

[ \text{either } A[i] > A[i-1] \text{ and } A[i] > A[i+1], \quad \text{or} \quad A[i] < A[i-1] \text{ and } A[i] < A[i+1]. ]

Note that the rearrangement must preserve the multiset of heights (i.e. the sum and frequency of the elements remain unchanged).

If the array contains only one element, output it as is. For a two-element array, any order is acceptable.

Your solution should read the input from standard input and output the result to standard output.

inputFormat

The first line of input contains an integer N (1 ≤ N ≤ 10^5), the number of students. The second line contains N space-separated integers representing the heights of the students.

outputFormat

Output a single line containing N space-separated integers representing the rearranged heights that satisfy the required condition.## sample

5
5 3 8 6 2

2 5 3 8 6