Ослабление флота

시간 제한2초메모리 제한1024 MB

요약

남은 함선들의 중간값(짝수 개일 때는 두 가운데 값 중 작은 값)을 매번 제거하면서, 제거되는 순서대로 함선의 전력을 출력합니다.

난이도: 보통10점 중 4점
유형: 정렬, 구현, 이분 탐색
정답자: 아직 제출이 없습니다

문제

Кэрол Дэнверс, известная как Капитан Марвел противодействует флоту Скруллов. Каждый из кораблей Скруллов имеет определенную мощность, выраженную натуральным числом.

Кэрол считает, что настолько сильна, что может не только вывести из строя флот, но и немного развлечься. Внимательно изучив мощность корабля, она решила, что будет выводить их из строя в следующем порядке: каждый раз Кэрол будет атаковать тот корабль из неатакованных ранее, мощность которого является медианой мощностей оставшихся кораблей.

Медиану ряда чисел Кэрол вычисляет следующим образом:

Если количество чисел в ряду нечетно, то медиана --- число, стоящее посередине упорядоченного по возрастанию данного ряда.
Если количество чисел в ряду чётно, то медианой ряда является:
- Меньшее из двух стоящих посередине чисел упорядоченного по возрастанию данного ряда, если два средних различны.
- Любое из двух стоящих посередине чисел упорядоченного по возрастанию данного ряда, если два средних равны.

Помогите Капитану Марвел посчитать порядок, в котором нужно атаковать корабли.

입력

В первой строке дано одно натуральное число $n$ --- число кораблей во флоте Скруллов ( $1 \le n \le 10^5$ ).

Во второй строке содержатся $n$ натуральных чисел $a\_i$ --- мощность $i$ -го корабля ( $1 \le a\_i \le 10^9$ ).

출력

Выведите $n$ чисел --- мощности кораблей в том порядке, в котором Кэрол будет их атаковать.

예제2

예제 1
입력
```
3
8 3 19
```
예상 출력
```
8 3 19
```
예제 2
입력
```
4
4 2 2 1
```
예상 출력
```
2 2 1 4
```