G. Множество с запросами
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас изначально множество $$$S$$$, которое изначально пустое. Также есть $$$q$$$ запросов трех типов:

  1. Добавить какое-то число в $$$S$$$. Гарантируется, что такого числа еще нет в множестве.
  2. Удалить какое-то число из $$$S$$$. Гарантируется, что такое число есть в множестве.
  3. Рассмотрим функцию $$$f(A) = max(A) - \frac{sum(A)}{2}$$$, где $$$max(A)$$$ — максимальное число в $$$A$$$, а $$$sum(A)$$$ — сумма чисел в $$$A$$$. Необходимо найти и вывести максимальное значение функции $$$f(A)$$$ по всем подмножествам $$$S$$$.
Входные данные

В первой строке дано число $$$q$$$ — количество запросов ($$$1 \le q \le 3 \cdot 10^5$$$). Затем следуют $$$q$$$ строк — сами запросы.

Если запрос первого типа, то будет введено 1 $$$val$$$ — это означает, что надо добавить число $$$val$$$ ($$$1 \le val \le 10^9$$$). Гарантируется, что такого числа еще нет. Гарантируется, что $$$val$$$ — это четное число.

Если запрос второго типа, то будет введено 2 $$$val$$$ — это означает, что надо удалить число $$$val$$$ ($$$1 \le val \le 10^9$$$). Гарантируется, что такое число сейчас есть в множестве.

Если запрос третьего типа, то будет введено 3 — после этого надо вывести максимальное значение $$$f(A)$$$ по всем подмножествам $$$S$$$. Гарантируется, что в этот момент $$$S$$$ не пустое.

Выходные данные

На каждый запрос типа 3 выведите максимальное значение функции, а затем перевод строки.

Примеры
Входные данные
5
1 30
3
1 40
1 10
3
Выходные данные
15
20
Входные данные
9
1 18
1 28
1 8
3
2 28
2 8
3
1 40
3
Выходные данные
14
9
20