问题描述

给定一个初始为空的序列S，你需要处理以下三种操作：

1. 1 x - 在序列末尾添加元素x
2. 2 - 删除序列末尾的元素（保证序列非空）
3. 3 - 查询当前序列中所有逆序对的数量

逆序对定义为序列中满足i < j且S[i] > S[j]的所有(i,j)对。

要求实现一个程序，处理最多500,000次操作，所有x的范围在1到500,000之间。

输入输出格式

​输入格式​：

• 第一行包含一个整数Q，表示操作数量
• 接下来Q行，每行一个操作

​输出格式​：

• 对于每个操作3，输出当前序列的逆序对数量

• 示例1

输入：

5
1 2
1 3
3
1 1
3

输出：

1
3

示例2

输入：

7
1 5
1 4
3
1 3
3
2
3

输出：

1
3
1

示例3

输入：

8
1 1
1 1
1 1
3
1 2
3
2
3

输出：

0
3
0

示例4

输入：

10
1 10
1 9
1 8
1 7
3
1 6
3
2
2
3

输出：

6
10
6

示例5

输入：

6
1 100000
1 99999
3
1 100000
3
2

输出：

1
1
1