冒泡排序是一种用于对序列进行排序的算法。假设我们要将长度为 $N$ 的序列 $A_0, A_1, \dots, A_{N-1}$ 按非递减顺序排序。冒泡排序在两个相邻数字顺序错误时交换它们。交换是通过重复遍历序列来完成的。具体来说，在一次遍历中，对于 $i = 0, 1, \dots, N - 2$，如果 $A_i > A_{i+1}$，我们就交换 $A_i$ 和 $A_{i+1}$。已知任何序列都可以通过若干次遍历按非递减顺序排序。对于序列 $A$，我们将冒泡排序的遍历次数定义为使用上述算法对 $A$ 进行排序所需的遍历次数。
JOI-kun 有一个长度为 $N$ 的序列 $A$。他将处理 $Q$ 个修改 $A$ 中数值的查询。具体来说，在第 $(j + 1)$ 次查询（$0 \le j \le Q - 1$）中，$A_{X_j}$ 的值被修改为 $V_j$。
JOI-kun 想要知道在处理完每次查询后，该序列进行冒泡排序所需的遍历次数。
样例
给定一个长度为 $N = 4$ 的序列 $A = \{1, 2, 3, 4\}$ 和 $Q = 2$ 次查询：$X = \{0, 2\}$，$V = \{3, 1\}$。
- 对于第一次查询，$A_0$ 的值变为 3。我们得到 $A = \{3, 2, 3, 4\}$。
- 对于第二次查询，$A_2$ 的值变为 1。我们得到 $A = \{3, 2, 1, 4\}$。
$A = \{3, 2, 3, 4\}$ 的冒泡排序： $A$ 未排序，因此开始第一次遍历。由于 $A_0 > A_1$，交换它们得到 $A = \{2, 3, 3, 4\}$。由于 $A_1 \le A_2$，不交换。由于 $A_2 \le A_3$，不交换。 现在 $A$ 已排序，冒泡排序结束。
因此，$A = \{3, 2, 3, 4\}$ 的冒泡排序遍历次数为 1。
$A = \{3, 2, 1, 4\}$ 的冒泡排序： $A$ 未排序，因此开始第一次遍历。由于 $A_0 > A_1$，交换它们得到 $A = \{2, 3, 1, 4\}$。由于 $A_1 > A_2$，交换它们得到 $A = \{2, 1, 3, 4\}$。由于 $A_2 \le A_3$，不交换。 $A$ 尚未排序，因此开始第二次遍历。由于 $A_0 > A_1$，交换它们得到 $A = \{1, 2, 3, 4\}$。由于 $A_1 \le A_2$，不交换。由于 $A_2 \le A_3$，不交换。 * 现在 $A$ 已排序，冒泡排序结束。
因此，$A = \{3, 2, 1, 4\}$ 的冒泡排序遍历次数为 2。
子任务
共有 4 个子任务。各子任务的分数和约束如下：
| 子任务 | 分数 | $N$ | $Q$ | $A, V$ |
|---|---|---|---|---|
| 1 | 17 | $1 \le N \le 2\,000$ | $1 \le Q \le 2\,000$ | $1 \le A_i, V_j \le 1\,000\,000\,000$ |
| 2 | 21 | $1 \le N \le 8\,000$ | $1 \le Q \le 8\,000$ | $1 \le A_i, V_j \le 1\,000\,000\,000$ |
| 3 | 22 | $1 \le N \le 50\,000$ | $1 \le Q \le 50\,000$ | $1 \le A_i, V_j \le 100$ |
| 4 | 40 | $1 \le N \le 500\,000$ | $1 \le Q \le 500\,000$ | $1 \le A_i, V_j \le 1\,000\,000\,000$ |
实现细节
你需要实现以下函数 countScans 来回答 $Q$ 个查询。
countScans(A, X, V)A: 长度为 $N$ 的整数数组，表示序列的初始值。X,V: 长度为 $Q$ 的整数数组，表示查询。- 该函数应返回一个长度为 $Q$ 的整数数组 $S$。对于每个 $0 \le j \le Q - 1$，$S_j$ 应为处理完第 $(j + 1)$ 次查询后，该序列进行冒泡排序所需的遍历次数。
样例
样例评测程序按以下格式读取输入：
- 第 1 行：$N \ Q$
- 第 2 行：$A_0 \ A_1 \ \dots \ A_{N-1}$
- 第 $3 + j$ 行（$0 \le j \le Q - 1$）：$X_j \ V_j$
样例评测程序按以下格式打印 countScans 的返回值：
- 第 $1 + j$ 行（$0 \le j \le Q - 1$）：$S_j$