H. Медиана потока

Числа приходят по одному. После каждого нового числа выведите медиану всех пришедших к этому моменту.

Если чисел чётное количество, медианой считается меньшее из двух средних.

Пересортировывать всё после каждого числа нельзя: чисел до $10^5$. Классическое решение — две кучи: в одной меньшая половина, в другой большая.

Первая строка содержит число $n$ ($1 \le n \le 10^5$).

Вторая строка содержит $n$ целых чисел, по модулю не превосходящих $10^9$.

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