28844번 - Ослабление флота 다국어

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

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

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

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

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

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

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

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