M. Медиана набора

В наборе лежат целые числа, возможно повторяющиеся; изначально он пуст. Операции: + x добавить число, - x удалить одно вхождение, ? вывести медиану.

Медианой набора из $k$ чисел называется элемент, стоящий на месте $\lceil k/2 \rceil$ в порядке неубывания. Запрос медианы пустого набора не встречается.

В первой строке — число операций $n$ ($1 \le n \le 2 \cdot 10^5$). В следующих $n$ строках — операции + x, - x или ?. Числа целые, по модулю не больше $10^9$.

На каждый запрос ? выведите медиану в отдельной строке.