题目描述

给定长度为 $n$ 的整数序列 $V$（下标从 $1$ 开始），支持以下两种操作/查询（操作/查询总数为 $Q$）：

• 1 x y（$1 \le x,y \le n$）：交换 $V_x$ 与 $V_y$。
• 2 l r（$1 \le l \le r \le n$）：求子序列 $V_{l \cdots r}$ 的逆序对数。

本题有 $T$ 组测试数据。

输入格式

$T$

$Case_1$

$Case_2$

$\vdots$

$Case_T$

其中，$Case_i$（$1 \le i \le T$）以以下格式给出：

$n$ $Q$

$V_1$ $V_2$ $\cdots$ $V_n$

$Query_1$

$Query_2$

$\vdots$

$Query_Q$

其中，$Query_i$（$1 \le i \le Q$）以以下两种格式之一给出（含义见题目描述）：

• 1 x y；
• 2 l r。

输出格式

对每个形如 2 l r 的操作，输出一行为所求子序列的逆序对数。

输入输出样例 #1

输入样例 #1

2
5 7
3 1 4 2 5
2 1 5
2 2 4
1 1 2
2 1 5
2 3 5
1 4 5
2 1 5
6 7
3 1 4 1 5 2
2 1 6
1 1 4
2 1 6
2 3 6
1 5 6
2 1 6
2 4 6

输出样例 #1

3
1
2
1
3
6
4
4
3
1

限制

对于所有测试数据：$1 \le n,Q \le 10^5$，$0 \le V_i \le 10^9$（$1 \le i \le n$）；

所有测试数据中 $n$ 的总和不大于 $10^5$，$Q$ 的总和不大于 $10^5$。