Median

Time limit2sMemory limit256 MB

Summary

Given a sequence, find the lexicographically largest permutation in which the median of every prefix is non-decreasing.

Level: Medium6 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

An integer sequence $a_1, a_2, \ldots, a_n$ is good if $m_1 \leq m_2 \leq \dots \leq m_n$ , where $m_i$ is the median of $a_1, a_2, \ldots, a_i$ .

Given a sequence $p_1, p_2, \dots, p_n$ , find a permutation of it that is good. If more than one exists, output the lexicographically largest one.

For a sequence $a_1, a_2, \ldots, a_k$ , the median is the $\lceil k/2 \rceil$ -th largest element when $k$ is odd. When $k$ is even, it is the average of the $k/2$ -th largest and the $(k/2+1)$ -th largest elements.

Input

The first line contains an integer $n$ ( $1 \leq n \leq 10^5$ ).

The second line contains $n$ integers $p_1, p_2, \ldots, p_n$ ( $1 \leq p_i \leq 10^9$ ).

Output

On the first line, print $n$ integers: the lexicographically largest good permutation of the input sequence.

Examples2

Example 1
Input
```
5
1 2 3 4 5
```
Expected output
```
1 3 2 5 4
```
Example 2
Input
```
8
1 2 2 3 3 3 4 4
```
Expected output
```
3 3 4 3 4 2 2 1
```