함대 약화

캡틴 마블로 알려진 캐롤 댄버스가 스크럴 함대에 맞선다. 스크럴 함대의 각 우주선에는 자연수로 나타낸 전투력이 있다.

캐롤은 함대를 무력화하는 데 그치지 않고 조금 즐길 만큼 자신이 강하다고 생각한다. 우주선의 전투력을 살핀 뒤, 다음 순서로 우주선을 공격하기로 했다. 매번 캐롤은 아직 공격하지 않은 우주선 전체의 전투력 중앙값과 같은 전투력을 가진 우주선을 골라 공격한다.

중앙값은 다음과 같이 구한다.

• 수의 개수가 홀수이면, 오름차순으로 정렬했을 때 가운데에 놓인 수가 중앙값이다.
• 수의 개수가 짝수이면, 오름차순으로 정렬했을 때 가운데 두 수가 후보가 된다. 두 수가 다르면 작은 쪽이 중앙값이고, 두 수가 같으면 어느 쪽을 골라도 중앙값이다.

첫 줄에 스크럴 함대의 우주선 수를 나타내는 자연수 $n$이 주어진다 ($1 \le n \le 10^5$).

둘째 줄에는 $i$번째 우주선의 전투력을 나타내는 자연수 $a_i$가 $n$개 주어진다 ($1 \le a_i \le 10^9$).

캐롤이 공격하는 순서대로 우주선의 전투력 $n$개를 출력한다.