중앙값

정수 수열 $a_1, a_2, \ldots, a_n$이 좋은 수열이라는 것은 $m_1 \leq m_2 \leq \dots \leq m_n$을 만족한다는 뜻입니다. 여기서 $m_i$는 $a_1, a_2, \ldots, a_i$의 중앙값입니다.

수열 $p_1, p_2, \dots, p_n$이 주어집니다. 이 수열을 재배열한 것 중 좋은 수열인 것을 하나 구하세요. 그런 재배열이 여러 개이면 사전순으로 가장 큰 것을 출력합니다.

수열 $a_1, a_2, \ldots, a_k$의 중앙값은 $k$가 홀수이면 큰 쪽에서 $\lceil k/2 \rceil$번째 원소입니다. $k$가 짝수이면 큰 쪽에서 $k/2$번째 원소와 $(k/2+1)$번째 원소의 평균입니다.

첫째 줄에 정수 $n$ ($1 \leq n \leq 10^5$)이 주어집니다.

둘째 줄에 정수 $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq 10^9$)이 $n$개 주어집니다.

첫째 줄에 주어진 수열을 재배열한 것 중 사전순으로 가장 큰 좋은 수열을 $n$개의 정수로 출력합니다.