← 返回题目列表

AtCoder · agc017_c

C. 潜伏和法术

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

有 N 连续球。 最初, i从左边数第一个球有整数 A_i 。 上面写着

当 Snuke 施展法术时,会发生以下情况:

  • 设当前球数为 k。所有的球都带有 上面写的 k 同时消失。

Snuke 的目标是通过多次施法来消除所有球。 这可能是不可能的。如果是这样的话,他想修改最小球数的整数,以实现他的目标。

顺便说一句,这些球上的整数有时会自行改变。 会有 M 这样的变化。在 j-th 变化,整数 X_j左边第一个球将变成 Y_j.

每次更改后,如果 Snuke 希望在下一次更改发生之前实现其目标,请找出球上整数修改的最小次数。我们假设他修改整数的速度足够快。在这里,请注意,他实际上并没有执行那些必要的修改,而是保持原样。

约束

  • 1 \leq N \leq 200000
  • 1 \leq M \leq 200000
  • 1 \leq A_i \leq N
  • 1 \leq X_j \leq N
  • 1 \leq Y_j \leq N

分值

  • 在测试集中值得 500 点, N \leq 200 和 M \leq 200.

输入

输入由标准输入按以下格式给出:

N M
A_1 A_2 ... A_N
X_1 Y_1
X_2 Y_2
:
X_M Y_M

输出

打印 M 行。 的 j第行应包含球上整数修改所需的最小数量,以使 Snuke 的目标可实现。


示例输入 1

5 3
1 1 3 4 5
1 2
2 5
5 4

示例输出 1

0
1
1
  • 第一次改变后,球上的整数变成 2, 1, 3, 4, 5,从左到右。在这里,通过施展五次咒语,所有的球都可以消失。因此,无需修改。
  • 第二次改变后,球上的整数变成 2, 5, 3, 4, 5,从左到右。在这种情况下,必须至少进行一项修改。一种最佳解决方案是将左起第五个球上的整数修改为 2,并施展该咒语四次。
  • 第三次改变后,球上的整数变成 2, 5, 3, 4, 4,从左到右。同样在这种情况下,必须进行至少一项修改。一种最佳解决方案是将左起第三个球上的整数修改为 2,并施展该咒语三次。

示例输入 2

4 4
4 4 4 4
4 1
3 1
1 1
2 1

示例输出 2

0
1
2
3

示例输入 3

10 10
8 7 2 9 10 6 6 5 5 4
8 1
6 3
6 2
7 10
9 7
9 9
2 4
8 1
1 8
7 7

示例输出 3

1
0
1
2
2
3
3
3
3
2