分数: 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