sort

题目描述

你有一个长为 $n$ 的序列 $a_{1..n}$。

一种排序方法是每次从前往后检查并交换，排序步数为这样操作的轮数，即下面伪代码中的cnt。

cnt = 0
while (没有排好序)
	for i = 1 .. n-1
		if (a[i] > a[i+1])
			swap(a[i], a[i+1])
	cnt += 1

有 $q$ 次单点修改 $a_i$，每次修改后，你都需要输出序列的 cnt值。

输入格式

一行两个整数 $n,q$。

接下来一行 $n$ 个整数，描述 $a_i$。

接下来 $q$ 行每行两个整数 $i,x$ 描述 $a_i\leftarrow x$ 的赋值操作。

输出格式

$q$ 行，每行一个整数表示答案。

样例输入

4 2
6 4 5 4
2 8
3 3

样例输出

3
2

数据范围

对于 $10\%$ 的数据，$n,q\leq 300$

对于另外 $20\%$ 的数据，$n,q\leq 3000$

对于另外 $20\%$ 的数据，$n,q\leq 50000$

对于另外 $20\%$ 的数据，$n,q\leq 2\cdot 10^5$

对于全部数据，$1\leq n,q\leq 5\cdot 10^5,1\le a_i,x\leq 5\cdot 10^5$。