题目描述

译自 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, Q$。

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

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

输出格式

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

4 2
1 2 3 4
0 3
2 1

1
2

样例 给定一个长度为 $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$。

数据规模与约定

$1 < N \leq 500000$

$1 < Q \leq 500000$

$1 < A_i, V_j \leq 10^9$