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

2000 мс · 256 МБ · всё или ничего

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

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

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

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

ввод

2
1 2

вывод

1 1

ввод

5
5 4 3 2 1

вывод

5 4 4 3 3

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.