시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 0 0 0 0.000%

문제

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.

예제 입력 1

5
1 2 3 4 5

예제 출력 1

1 3 2 5 4

예제 입력 2

8
1 2 2 3 3 3 4 4

예제 출력 2

3 3 4 3 4 2 2 1