题目描述

译自 JOI Open 2018 T1 「バブルソート 2 / Bubble Sort 2」

冒泡排序是一个对序列排序的算法。现在我们要将一个长度为 $N$ 的序列 $A_0,A_1,\ldots ,A_{N-1}$​ 按不降顺序排序。当两个相邻的数没有按正确顺序排列时，冒泡排序会交换这两个数的位置。每次扫描这个序列就进行这种交换。更确切地说，在一趟扫描中，对于 $i=0,1,\ldots ,N-2$，并按这个顺序，如果 $A_i>A_{i+1}$​，那么我们就交换这两个数的位置。众所周知任何序列经过有限趟扫描后一定可以按非降顺序排好序。对于一个序列 $A$，我们定义用冒泡排序的扫描趟数为使用如上算法使得 $A$ 排好序的情况下所扫描的趟数。

JOI 君有一个长度为 $N$ 的序列 $A$。他打算处理 $Q$ 次修改 $A$ 的值的询问。更明确地说，在第 $(j+1)\ (0\le j\le Q-1)$ 次询问，$A_{X_j}$ 的值会变为 $V_j$。

JOI 君想知道处理每次修改之后，用冒泡排序的扫描趟数。

样例

给定一个长度为 $N=4$ 的序列 $A=\{1,2,3,4\}$​ 和 $Q=2$ 次询问：$X=\{0,2\},V=\{3,1\}$。

1. 对于第一次询问，$A_0$ 的值变为 $3$。我们得到 $A=\{3,2,3,4\}$。
2. 对于第一次询问，$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$​​。

子任务

共有四个子任务。每个子任务的分值及附加限制如下：

实现细节

你需要实现如下函数 $\texttt{countScans}$ 回答 $Q$ 次询问。

• $\texttt{countScans(A, X, V)}$
  • $\texttt{A}$：长度为 $N$​ 的整数数组，表示序列的初始值。
  • $\texttt{X, V}$：长度为 $Q$ 的整数数组，表示每次询问。
  • 这个函数应当返回一个长度为 $S$ 的数组 $Q$。对于每个 $0\le j\le Q-1$，$S_j$ 代表处理第 $(j+1)$ 个询问后，对这个序列冒泡排序的扫描趟数。

C++ 的提交应引入库 $\texttt{bubblesort2.h}$ 来完成，目前不支持对 Java 和 Pascal 语言提交的测评。

样例交互器

样例交互器按如下格式读入输入：

第一行两个整数 $N,Q$。

第二行 $N$ 个整数 $A_0,A_1,\ldots ,A_{N-1}$。

接下来 $Q$ 行，每行两个整数 $X_j,V_j$。

样例交互器按如下格式输出函数 $\texttt{countScans}$ 的返回值：

输出 $Q$ 行，第 $(j+1)\ (0\le j\le Q-1)$ 行表示 $S_j$。