E2. Откаты (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное отличие между простой и сложной версиями в том, что в сложной версии вы должны отвечать на запросы в режиме онлайн. Вы можете делать взломы, только если обе версии задачи решены.

У вас есть массив $$$a$$$, изначально пустой. Вам нужно обрабатывать запросы следующих типов:

  • + $$$x$$$ — добавить число $$$x$$$ в конец массива $$$a$$$.
  • - $$$k$$$ — удалить $$$k$$$ последних чисел из массива $$$a$$$.
  • ! — откатить последнее действующее изменение (т. е. сделать массив $$$a$$$ таким, каким он был до изменения). В данной задаче изменениями считаются только запросы первых двух типов (+ и -).
  • ? — найти количество различных чисел в массиве $$$a$$$.
Входные данные

В первой строке задано одно целое число $$$q$$$ ($$$1 \leq q \leq 10^6$$$) — количество запросов.

В следующих $$$q$$$ строках даны запросы в формате, описанном выше.

Гарантируется, что

  • в запросах первого типа $$$1 \le x \le 10^6$$$;
  • в запросах второго типа $$$k \ge 1$$$ и $$$k$$$ не превосходит текущей длины массива $$$a$$$;
  • в момент запроса третьего типа есть хотя бы один запрос первого или второго типа, который можно откатить.

Также гарантируется, что количество запросов четвёртого вида (?) не превосходит $$$10^5$$$.

Обратите внимание, что вы должны решить данную задачу в режиме онлайн. То есть вы не можете считать все входные данные заранее. Вы можете считать очередной запрос только после того как выведете ответ на предыдущий, поэтому не забывайте сбрасывать поток вывода после вывода ответа. Вы можете использовать такие функции как fflush(stdout) в C++, BufferedWriter.flush в Java или похожие после каждого вывода в программе.

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

Для каждого запроса четвёртого типа выведите одно целое число: количество различных элементов в массиве $$$a$$$ в момент запроса.

Примеры
Входные данные
10
+ 1
+ 2
+ 2
?
!
+ 3
- 2
?
+ 1
?
Выходные данные
2
1
1
Входные данные
6
+ 1
+ 1000000
?
!
!
?
Выходные данные
2
0
Примечание

В первом тесте из условия массив $$$a$$$ изменяется следующим образом:

  1. После первого запроса $$$a=[1]$$$.
  2. После второго запроса $$$a=[1,2]$$$.
  3. После третьего запроса $$$a=[1,2,2]$$$.
  4. В момент четвёртого запроса в массиве $$$a$$$ встречаются $$$2$$$ различных числа: $$$1$$$ и $$$2$$$.
  5. После пятого запроса $$$a=[1,2]$$$ (откатили изменение + 2).
  6. После шестого запроса $$$a=[1,2,3]$$$.
  7. После седьмого запроса $$$a=[1]$$$.
  8. В момент восьмого запроса массиве $$$a$$$ состоит только из одной $$$1$$$.
  9. После девятого запроса $$$a=[1,1]$$$.
  10. В момент десятого запроса массиве $$$a$$$ состоит только из двух $$$1$$$.

Во втором тесте из условия массив $$$a$$$ изменяется следующим образом:

  1. После первого запроса $$$a=[1]$$$.
  2. После второго запроса $$$a=[1, 1\,000\,000]$$$.
  3. В момент третьего запроса в массиве $$$a$$$ встречаются $$$2$$$ различных числа: $$$1$$$ и $$$1\,000\,000$$$.
  4. После четвёртого запроса $$$a=[1]$$$ (откатили изменение + 1000000).
  5. После пятого запроса $$$a=[]$$$ (откатили изменение + 1).
  6. В момент шестого запроса в массиве $$$a$$$ нет чисел, поэтому ответ на этот запрос равен $$$0$$$.