Олимпиадный тренинг

Задача 33252. Weakening of the fleet


Задача

Темы: "Два указателя"
Carol Danvers, known as Captain Marvel, counters the Skrull fleet. Each of
Skrull ships have a certain amount of power expressed as a natural number.
Carol thinks she's so strong that she can not only disable the fleet, but also a little
have fun. After carefully studying the power of the ship, she decided that she would disable them
in the following order: each time Carol will attack the ship that was not attacked before,
whose power is the median of the power of the remaining ships.
Carol calculates the median of a series of numbers as follows:
• If the number of numbers in the row is odd, then the median — the number in the middle of the given series sorted in ascending order.
• If the number of numbers in a row is even, then the median of the row is:
– The smaller of the two numbers in the middle of the given series, sorted in ascending order, if the two middle numbers are different.
– Any of the two numbers in the middle of the given series, sorted in ascending order,
if two means are equal.
Help Captain Marvel figure out the order in which to attack the ships.

Input data format
The first line contains one natural number n — number of ships in the Skrull fleet (1 <= n <= 105).
The second line contains n natural numbers ai — power of i-th ship (1 <= ai <=109).
Output format
Print n numbers — the power of the ships in the order that Carol will attack them.
 
Input Output
3
8 3 19
 
8 3 19
4
4 2 2 1
2 2 1 4