E1. Откаты (простая версия)
ограничение по времени на тест
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$$$.

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

Для каждого запроса четвёртого типа выведите одно целое число: количество различных элементов в массиве $$$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$$$.