Alternate Card Sorting

You are given a deck of cards with numbers. The deck has \( n \) cards. Divide the deck into two parts:

• The first part contains the first \( \lfloor \frac{n}{2} \rfloor \) cards.
• The second part contains the remaining cards.

Sort each part in ascending order separately. Then, merge the two sorted parts alternately by taking one card from the first part and then one from the second part. If one part is exhausted, append the remaining cards of the other part to the result.

For example, if \( n = 4 \) and the cards are [13, 7, 5, 1], the first part [13, 7] sorted becomes [7, 13], and the second part [5, 1] sorted becomes [1, 5]. Alternately merging these gives [7, 1, 13, 5].

inputFormat

The input is read from standard input. The first line contains an integer ( n ) ( (1 \le n \le 10^5) ) representing the number of cards. The second line contains ( n ) space-separated integers representing the card numbers.

outputFormat

Output to standard output the final merged sequence of card numbers in one line, with each number separated by a space.## sample

4
13 7 5 1

7 1 13 5