310606: CF1858E2. Rollbacks (Hard Version)

E2. Rollbacks (Hard Version)time limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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$.

Input

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.

Output

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

ExamplesInput

10
+ 1
+ 2
+ 2
?
!
+ 3
- 2
?
+ 1
?

Output

2
1
1

Input

6
+ 1
+ 1000000
?
!
!
?

Output

2
0

Note

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. + x —— 在数组a的末尾添加整数x。
2. - k —— 从数组a的末尾移除最后k个数字。
3. ! —— 撤销最后一个有效变更（即，使数组a恢复到变更之前的状态）。在这个问题中，只有前两种类型的查询（+和-）被视为变更。
4. ? —— 查找数组a中不同数字的数量。

输入数据格式：
- 第一行包含一个整数q（1≤q≤10^6）——查询的数量。
- 接下来的q行包含上述描述的查询。
- 在第一种类型的查询中，1≤x≤10^6；
- 在第二种类型的查询中，k≥1且k不大于数组a当前的长度；
- 在第三种类型的查询发生时，至少有一个第一种或第二种类型的查询可以被撤销。
- 第四种类型查询的数量（?）不超过10^5。

输出数据格式：
- 对于每个第四种类型的查询，输出一个整数——查询时刻数组a中不同元素的数量。

注意：你需要在线解决问题，这意味着你不能一次读取整个输入。你只能在写出最后一个查询的答案后读取每个查询，所以在打印答案后别忘了刷新输出。你可以在C++中使用像fflush(stdout)这样的函数，在Java中使用BufferedWriter.flush，或在你程序中的每次写入后使用类似的方法。

示例：

输入：
```
10
+ 1
+ 2
+ 2
?
!
+ 3
- 2
?
+ 1
?
```
输出：
```
2
1
1
```

输入：
```
6
+ 1
+ 1000000
?
!
!
?
```
输出：
```
2
0
```

在第一个示例中，数组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个1。
- 第九个查询后，a=[1,1]。
- 第十个查询时，数组a中有2个1。

在第二个示例中，数组a的变化如下：
- 第一个查询后，a=[1]。
- 第二个查询后，a=[1, 1000000]。
- 第三个查询时，数组a中有2个不同的整数：1和1000000。
- 第四个查询后，a=[1]（撤销了变更+ 1000000）。
- 第五个查询后，a=[]（撤销了变更+ 1）。
- 第六个查询时，数组a中没有整数，所以这个查询的答案是0。题目大意：这是一个困难版本的题目，与简单版本的区别在于你需要在线处理查询。你有一个初始为空的数组a，需要处理以下几种类型的查询： 1. + x —— 在数组a的末尾添加整数x。 2. - k —— 从数组a的末尾移除最后k个数字。 3. ! —— 撤销最后一个有效变更（即，使数组a恢复到变更之前的状态）。在这个问题中，只有前两种类型的查询（+和-）被视为变更。 4. ? —— 查找数组a中不同数字的数量。 输入数据格式： - 第一行包含一个整数q（1≤q≤10^6）——查询的数量。 - 接下来的q行包含上述描述的查询。 - 在第一种类型的查询中，1≤x≤10^6； - 在第二种类型的查询中，k≥1且k不大于数组a当前的长度； - 在第三种类型的查询发生时，至少有一个第一种或第二种类型的查询可以被撤销。 - 第四种类型查询的数量（?）不超过10^5。 输出数据格式： - 对于每个第四种类型的查询，输出一个整数——查询时刻数组a中不同元素的数量。 注意：你需要在线解决问题，这意味着你不能一次读取整个输入。你只能在写出最后一个查询的答案后读取每个查询，所以在打印答案后别忘了刷新输出。你可以在C++中使用像fflush(stdout)这样的函数，在Java中使用BufferedWriter.flush，或在你程序中的每次写入后使用类似的方法。 示例： 输入： ``` 10 + 1 + 2 + 2 ? ! + 3 - 2 ? + 1 ? ``` 输出： ``` 2 1 1 ``` 输入： ``` 6 + 1 + 1000000 ? ! ! ? ``` 输出： ``` 2 0 ``` 在第一个示例中，数组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个1。 - 第九个查询后，a=[1,1]。 - 第十个查询时，数组a中有2个1。 在第二个示例中，数组a的变化如下： - 第一个查询后，a=[1]。 - 第二个查询后，a=[1, 1000000]。 - 第三个查询时，数组a中有2个不同的整数：1和1000000。 - 第四个查询后，a=[1]（撤销了变更+ 1000000）。 - 第五个查询后，a=[]（撤销了变更+ 1）。 - 第六个查询时，数组a中没有整数，所以这个查询的答案是0。