Sort and Merge Marbles

You are given an even number of marbles represented by their unique integer sizes. The marbles are split equally into two parts. Your task is to sort each part in descending order independently, and then merge the two sorted sequences into one overall descending order list.

More formally, given a list of n integers (where n is even), split the list into two parts of size n/2. Let the first part be sorted in descending order and similarly the second part be sorted in descending order. Then, merge these two sorted halves to obtain one final list that is also sorted in descending order using a two-pointer technique.

Note: The input is provided via standard input (stdin) and the output should be written to standard output (stdout).

Example:

Input:
6
12 7 5 3 14 8
Output:
14 12 8 7 5 3

</p>

inputFormat

The input is read from stdin and has the following format:

1. The first line contains a single integer n (where n is even) denoting the number of marbles.
2. The second line contains n space-separated integers representing the sizes of the marbles.

outputFormat

Output the merged list of marbles sorted in descending order on a single line, with the numbers separated by a space. The output should be written to stdout.

## sample

6
12 7 5 3 14 8

14 12 8 7 5 3

</p>