Задача F. Золотая середина

Автор:И. Бураго   Ограничение времени:3 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Центральным элементом набора из k чисел называется такой элемент, который после сортировки набора будет занимать в нём центральную позицию (то есть позицию номер k / 2, считая с единицы).

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

Формат входного файла

Входной файла содержит количество чисел n, за которым следуют n целых чисел ai в порядке их добавления в набор.

Формат выходного файла

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

Ограничения

1 ≤ n ≤ 106,  − 109 ≤ ai ≤ 109.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
5 3 4
5 3 4
2
5
1 2 3 2 4
1 1 2 2 2

0.038s 0.009s 15