You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

巡给你一个 $1\sim n$ 的排列 $p$，维护两种操作：

• 1 x 交换 $p_x,p_{x+1}$。
• 2 x 求出当前排列经过 $x$ 轮冒泡排序后的逆序对个数。

对一个长度为 $n$ 的排列 $p_i$ 进行一轮冒泡排序的伪代码如下：

for(int i=1;i<n;i++) 
    if(a[i]>a[i+1]) 
        swap(a[i],a[i+1]);

输入格式

第一行两个整数 $n$，$m$，表示排列长度与操作个数。

第二行 $n$ 个整数表示排列 $p_i$。

接下来 $m$ 行每行两个整数 $o_i,x_i$，描述一次操作。

输出格式

对于每次询问操作输出一行一个整数表示答案。

样例

【样例输入】

3 6
1 2 3
2 0
1 1
1 2
2 0
2 1
2 2

【样例输出】

0
2
1
0

数据范围

对于测试点 $1 ∼ 2$：$n,m \leq 100$。

对于测试点 $3 ∼ 4$：$n,m \leq 2000$。

对于测试点 $5 ∼ 6$：交换操作个数不超过 $100$。

对于所有测试点：$2 \leq n,m \leq 2 \times 10^5$，$o_i \in \{1,2\}$。

• 若 $o_i=1$，则 $1\leq x< n$；
• 否则，$0\leq x\leq 2^{32}-1$.