Это простая версия задачи. Единственное отличие между простой и сложной версиями в том, что в сложной версии вы должны отвечать на запросы в режиме онлайн. Вы можете делать взломы, только если обе версии задачи решены.
У вас есть массив $$$a$$$, изначально пустой. Вам нужно обрабатывать запросы следующих типов:
- + $$$x$$$ — добавить число $$$x$$$ в конец массива $$$a$$$.
- - $$$k$$$ — удалить $$$k$$$ последних чисел из массива $$$a$$$.
- ! — откатить последнее действующее изменение (т. е. сделать массив $$$a$$$ таким, каким он был до изменения). В данной задаче изменениями считаются только запросы первых двух типов (+ и -).
- ? — найти количество различных чисел в массиве $$$a$$$.
Выходные данные
Для каждого запроса четвёртого типа выведите одно целое число: количество различных элементов в массиве $$$a$$$ в момент запроса.
Примечание
В первом тесте из условия массив $$$a$$$ изменяется следующим образом:
- После первого запроса $$$a=[1]$$$.
- После второго запроса $$$a=[1,2]$$$.
- После третьего запроса $$$a=[1,2,2]$$$.
- В момент четвёртого запроса в массиве $$$a$$$ встречаются $$$2$$$ различных числа: $$$1$$$ и $$$2$$$.
- После пятого запроса $$$a=[1,2]$$$ (откатили изменение + 2).
- После шестого запроса $$$a=[1,2,3]$$$.
- После седьмого запроса $$$a=[1]$$$.
- В момент восьмого запроса массиве $$$a$$$ состоит только из одной $$$1$$$.
- После девятого запроса $$$a=[1,1]$$$.
- В момент десятого запроса массиве $$$a$$$ состоит только из двух $$$1$$$.
Во втором тесте из условия массив $$$a$$$ изменяется следующим образом:
- После первого запроса $$$a=[1]$$$.
- После второго запроса $$$a=[1,1\,000\,000]$$$.
- В момент третьего запроса в массиве $$$a$$$ встречаются $$$2$$$ различных числа: $$$1$$$ и $$$1\,000\,000$$$.
- После четвёртого запроса $$$a=[1]$$$ (откатили изменение + 1000000).
- После пятого запроса $$$a=[]$$$ (откатили изменение + 1).
- В момент шестого запроса в массиве $$$a$$$ нет чисел, поэтому ответ на этот запрос равен $$$0$$$.