Это сложная версия задачи. Единственное отличие между простой и сложной версиями в том, что в сложной версии вы должны отвечать на запросы в режиме онлайн. Вы можете делать взломы, только если обе версии задачи решены.
У вас есть массив \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
+ 1
+ 2
+ 2
?
!
+ 3
- 2
?
+ 1
?
|
2
1
1
|
|
2
|
6
+ 1
+ 1000000
?
!
!
?
|
2
0
|