K. Медиана: большее из двух средних

Как классная задача про медиану потока, но при чётном количестве чисел выведите большее из двух средних.

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

и брать ответ из корня правой (min-)кучи.

Задача выглядит косметической, и в этом её польза: если ваше классное решение было написано «как получилось», а не по инварианту, переделать его будет мучительно. Если по инварианту - изменится одна строка.

Проверьте на потоке $1, 2$: после первого числа ответ 1, после второго - 2.

В первой строке - число $n$ ($1 \le n \le 2 \cdot 10^5$).

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

Выведите $n$ чисел - медиану после каждого пришедшего.