#P10329. sort

    ID: 9447 传统题 2000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-冒泡排序支配关系一维前缀和懒标记线段树有序集合

sort

sort

题目描述

你有一个长为 nn 的序列 a1..na_{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

有 qq 次单点修改 aia_i,每次修改后,你都需要输出序列的 cnt值。

输入格式

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

接下来一行 nn 个整数,描述 aia_i。

接下来 qq 行每行两个整数 i,xi,x 描述 ai←xa_i\leftarrow x 的赋值操作。

输出格式

qq 行,每行一个整数表示答案。

样例输入

4 2
6 4 5 4
2 8
3 3

样例输出

3
2

数据范围

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

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

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

对于另外 20%20\% 的数据,n,q≤2⋅105n,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$。