Биржевой шлюз обрабатывает поток заявок. Требуется после каждого запроса сообщать медианную цену среди всех заявок, поступивших к этому моменту.
Формат ввода
В первой строке — число операций $n$ ($1 \le n \le 200000$).
Далее $n$ строк, каждая одного из двух видов:
+ x— поступила заявка с ценой $x$ ($1 \le x \le 1000000000$);?— запрос медианы.
Гарантируется, что перед первым запросом ? поступила хотя бы одна заявка.
Формат вывода
На каждый запрос ? выведите медиану цен всех поступивших заявок, по одному числу в
строке.
Если количество заявок нечётно, медиана — это средний элемент отсортированной последовательности. Если чётно — меньший из двух средних. Ответ всегда целое число.
Замечание
Наивное решение, сортирующее накопленный список на каждый запрос, не уложится в ограничение по времени.