CF1858E2.Rollbacks (Hard Version)

This is a hard version of this problem. The only difference between the versions is that you have to solve the hard version in online mode. You can make hacks only if both versions of the problem are solved.

You have an array $a$, which is initially empty. You need to process queries of the following types:

• • $x$ — add the integer $x$ to the end of the array $a$.
• - $k$ — remove the last $k$ numbers from the array $a$.
• ! — roll back the last active change (i.e., make the array $a$ the way it was before the change). In this problem, only queries of the first two types (+ and -) are considered as changes.
• ? — find the number of distinct numbers in the array $a$.

本题是该问题的困难版本。两个版本的唯一区别在于，你必须以在线模式解决困难版本。仅当两个版本的问题均被解决时，你才可以进行 hack。

你有一个数组 $a$，初始为空。你需要处理以下类型的查询：

• • $x$ — 将整数 $x$ 添加到数组 $a$ 的末尾；
• - $k$ — 从数组 $a$ 的末尾移除最后 $k$ 个数；
• ! — 回滚上一次生效的修改（即让数组 $a$ 恢复为该次修改前的状态）。在本题中，仅前两种类型的查询（+ 和 -）被视为修改；
• ? — 查询数组 $a$ 中不同数字的个数。

The first line contains an integer $q$ ($1 \leq q \leq 10^6$) — the number of queries.

The next $q$ lines contain the queries as described above.

It is guaranteed that

• in the queries of the first type, $1 \le x \le 10^6$;
• in the queries of the second type, $k \ge 1$ and $k$ does not exceed the current length of the array $a$;
• at the moment of the queries of the third type, there is at least one query of the first or of the second type that can be rolled back.

It is also guaranteed that the number of queries of the fourth type (?) does not exceed $10^5$.

Note that you should solve the problem in online mode. It means that you can't read the whole input at once. You can read each query only after writing the answer for the last query, so don't forget to flush output after printing answers. You can use functions like fflush(stdout) in C++ and BufferedWriter.flush in Java or similar after each writing in your program.

第一行包含一个整数 $q$（$1 \leq q \leq 10^6$），表示查询的数量。

接下来的 $q$ 行按上述描述给出各查询。

保证满足以下条件：

• 对于第一类查询，有 $1 \le x \le 10^6$；
• 对于第二类查询，有 $k \ge 1$，且 $k$ 不超过当前数组 $a$ 的长度；
• 在执行第三类查询时，至少存在一个第一类或第二类查询可供撤销（回滚）。

还保证第四类查询（?）的数量不超过 $10^5$。

注意：本题需以在线模式求解。这意味着你不能一次性读入全部输入；你必须在输出上一个查询的答案之后，才能读入下一个查询。因此，请务必在每次输出答案后刷新输出缓冲区。在 C++ 中可使用 fflush(stdout)，Java 中可使用 BufferedWriter.flush()，或其他编程语言中对应的刷新函数。

For each query of the fourth type output one integer — the number of distinct elements in array $a$ at the moment of query.

对于每个第四类查询，输出一个整数——查询时刻数组 $a$ 中不同元素的个数。

In the first example array $a$ changes as follows:

1. After the first query, $a=[1]$.
2. After the second query, $a=[1,2]$.
3. After the third query, $a=[1,2,2]$.
4. At the moment of the fourth query, there are $2$ distinct intergers in the array $a$: $1$ and $2$.
5. After the fifth query, $a=[1,2]$ (rolled back the change + 2).
6. After the sixth query, $a=[1,2,3]$.
7. After the seventh query, $a=[1]$.
8. At the moment of the eigth query, there is only one $1$ in the array $a$.
9. After the ninth query, $a=[1,1]$.
10. At the moment of the tenth query, there are only two $1$ in the array $a$.

In the second example array $a$ changes as follows:

1. After the first query, $a=[1]$.
2. After the second query, $a=[1, 1\,000\,000]$.
3. At the moment of the third query, there are $2$ distinct intergers in the array $a$: $1$ and $1\,000\,000$.
4. After the fourth query, $a=[1]$ (rolled back the change + 1000000).
5. After the fifth query, $a=[]$ (rolled back the change + 1).
6. At the moment of the sixth query, there are no integers in the array $a$, so the answer to this query is $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$。