310605: CF1858E1. Rollbacks (Easy Version)

E1. Rollbacks (Easy Version)time limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is an easy 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$.

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

题目大意：这是一个关于数组操作的问题，数组初始为空。需要处理以下几种类型的查询：

1. `+ x`：将整数x添加到数组a的末尾。
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中不同元素的数量。

示例：

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

注意：在第一个示例中，数组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,1,000,000]。
- 第三个查询时刻，数组a中有2个不同的整数：1和1,000,000。
- 第四个查询后，a=[1]（撤销了+ 1,000,000的更改）。
- 第五个查询后，a=[]（撤销了+ 1的更改）。
- 第六个查询时刻，数组a中没有整数，所以这个查询的答案是0。题目大意：这是一个关于数组操作的问题，数组初始为空。需要处理以下几种类型的查询： 1. `+ x`：将整数x添加到数组a的末尾。 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中不同元素的数量。 示例： 输入： ``` 10 + 1 + 2 + 2 ? ! + 3 - 2 ? + 1 ? ``` 输出： ``` 2 1 1 ``` 注意：在第一个示例中，数组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,1,000,000]。 - 第三个查询时刻，数组a中有2个不同的整数：1和1,000,000。 - 第四个查询后，a=[1]（撤销了+ 1,000,000的更改）。 - 第五个查询后，a=[]（撤销了+ 1的更改）。 - 第六个查询时刻，数组a中没有整数，所以这个查询的答案是0。