Optimal Game Sequence

Alice and Bob are playing a game with a sequence of n integers. Initially, there are n integers, and both players take turns picking the largest remaining integer until none are left. The twist is that both players are playing optimally, and each always picks the largest available value when it is their turn. The final sequence is determined by the order in which the numbers are picked.

The problem is equivalent to sorting the list in descending order. Formally, given an integer \( n \) and a sequence \( a_1,a_2,\dots,a_n \), the final sequence is:

[ a_{{i_1}} \ge a_{{i_2}} \ge \cdots \ge a_{{i_n}} ]

Your task is to compute the final sequence.

inputFormat

The input is read from standard input (stdin) and consists of two lines. The first line contains an integer n (the number of integers). The second line contains n space-separated integers representing the initial sequence.

outputFormat

Output the final sequence as a single line of n space-separated integers (from standard output, stdout).

4
9 6 1 2

9 6 2 1