19322번 - Median 다국어

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 its permutation which is good. If the result is not unique, find the lexicographically largest one.

For a sequence $a_1, a_2, \ldots, a_n$, the median is the $\lceil n/2 \rceil$-th largest element if $n$ is odd, or the average of the $n/2$-th largest and the $(n/2+1)$-th largest elements if $n$ is even.

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$).

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