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

Для набора из k чисел медианой считается элемент, стоящий на позиции (k - 1) / 2 в отсортированном порядке, то есть используется нижняя медиана.

Требуется по заданной последовательности измерений определить, какое значение датчик должен сообщить после каждого измерения.

Входные данные

Первая строка содержит целое число n — количество измерений.

Вторая строка содержит n целых чисел a_i — результаты измерений в порядке их поступления.

Выходные данные

Выведите n чисел — медиану после каждого очередного измерения, по одному в строке.

Ограничения

• 1 <= n <= 2 * 10^5
• |a_i| <= 10^9

Примеры

Пример 1

Входные данные

1
5

Выходные данные

5

Пример 2

Входные данные

5
1 2 3 4 5

Выходные данные

1
1
2
2
3