{"raw_statement":[{"iden":"statement","content":"冒泡排序是一个对序列排序的算法。现在我们要将一个长度为 $N$ 的序列 $A_0,A_1,\\ldots ,A_{N-1}$​ 按不降顺序排序。当两个相邻的数没有按正确顺序排列时，冒泡排序会交换这两个数的位置。每次扫描这个序列就进行这种交换。更确切地说，在一趟**扫描**中，对于 $i=0,1,\\ldots ,N-2$，并按这个顺序，如果 $A_i>A_{i+1}$​，那么我们就交换这两个数的位置。众所周知任何序列经过有限趟扫描后一定可以按非降顺序排好序。对于一个序列 $A$，我们定义**用冒泡排序的扫描趟数**为使用如上算法使得 $A$ 排好序的情况下所扫描的趟数。\n\nJOI 君有一个长度为 $N$ 的序列 $A$。他打算处理 $Q$ 次修改 $A$ 的值的询问。更明确地说，在第 $(j+1)\\ (0\\le j\\le Q-1)$ 次询问，$A_{X_j}$ 的值会变为 $V_j$。\n\nJOI 君想知道处理每次修改之后，用冒泡排序的扫描趟数。"},{"iden":"input","content":"LOJ 上为交互题，方便起见，这里使用传统题的方式进行评测。\n\n第一行两个整数 $N,Q$。\n\n第二行 $N$ 个整数 $A_0,A_1,\\ldots ,A_{N-1}$。\n\n接下来 $Q$ 行，每行两个整数 $X_j,V_j$。"},{"iden":"output","content":"输出 $Q$ 行，第 $(j+1)\\ (0\\le j\\le Q-1)$ 行表示处理第 $(j+1)$ 个询问后，对这个序列冒泡排序的扫描趟数。"},{"iden":"note","content":"**【样例解释】**\n\n给定一个长度为 $N=4$ 的序列 $A=\\{1,2,3,4\\}$ 和 $Q=2$ 次询问：$X=\\{0,2\\},V=\\{3,1\\}$。\n\n1. 对于第一次询问，$A_0$ 的值变为 $3$。我们得到 $A=\\{3,2,3,4\\}$。\n2. 对于第一次询问，$A_2$ 的值变为 $1$。我们得到 $A=\\{3,2,1,4\\}$。\n\n对 $A=\\{3,2,3,4\\}$ 做冒泡排序：\n\n- $A$ 并未排好序，所以第一趟扫描开始。因为 $A_0>A_1$，所以我们交换它们，序列变为 $A=\\{2,3,3,4\\}$。因为 $A_1\\le A_2$，所以我们不交换它们。因为 $A_2\\le A_3$，所以我们也不交换它们。\n- 现在 $A$ 已经排好序了，所以冒泡排序过程结束。\n\n因此对于 $A=\\{3,2,3,4\\}$，冒泡排序的扫描趟数为 $1$。\n\n对 $A=\\{3,2,1,4\\}$ 做冒泡排序：\n\n- $A$ 并未排好序，所以第一趟扫描开始。因为 $A_0>A_1$，所以我们交换它们，序列变为 $A=\\{2,3,1,4\\}$。因为 $A_1> A_2$，所以我们交换它们，序列变为 $A=\\{2,1,3,4\\}$。因为 $A_2\\le A_3$，所以我们也不交换它们。\n- $A$ 并未排好序，所以第二趟扫描开始。因为 $A_0>A_1$，所以我们交换它们，序列变为 $A=\\{1,2,3,4\\}$。因为 $A_1\\le A_2$，所以我们不交换它们。因为 $A_2\\le A_3$，所以我们也不交换它们。\n- 现在 $A$ 已经排好序了，所以冒泡排序过程结束。\n\n因此对于 $A=\\{3,2,1,4\\}$，冒泡排序的扫描趟数为 $2$。\n\n**【数据范围】**\n\n共有四个子任务。每个子任务的分值及附加限制如下：\n\n| 子任务编号 | 分值 |         $N$          |         $Q$          |              $A,V$               |\n| :--------: | :--: | :------------------: | :------------------: | :------------------------------: |\n|    $1$     | $17$ |  $1\\le N\\le 2\\ 000$  |  $1\\le Q\\le 2\\ 000$  |      $1\\le A_i,V_j\\le 10^9$      |\n|    $2$     | $21$ |  $1\\le N\\le 8\\ 000$  |  $1\\le Q\\le 8\\ 000$  | $1\\le A_i,V_j\\le 10^9$ |\n|    $3$     | $22$ | $1\\le N\\le 50\\ 000$  | $1\\le Q\\le 50\\ 000$  |      $1\\le A_i,V_j\\le 100$       |\n|    $4$     | $40$ | $1\\le N\\le 500\\ 000$ | $1\\le Q\\le 500\\ 000$ |      $1\\le A_i,V_j\\le 10^9$      |\n\n"}],"translated_statement":null,"sample_group":[["4 2\n1 2 3 4\n0 3\n2 1","1\n2"],["11 12\n11 4 13 6 7 3 5 12 4 10 11\n8 11\n4 4\n6 20\n0 2\n7 2\n3 18\n5 9\n0 6\n8 8\n9 4\n0 8\n6 18\n","5\n5\n5\n4\n6\n6\n6\n7\n7\n7\n7\n7"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}