[AGC017C] Snuke and Spells

$N$ 个球排在一起，每个球上有一个数 $a_i$。接下来会进行若干轮删除。设现在还有 $k$ 个球，则 $a_i=k$ 的球会被删除。 最终可能球不会被删完，你需要求出最少修改几个球上的数后可以让球全部被删完。 同时还有 $M$ 次修改，每次修改第 $X_i$ 个球的数为 $Y_i$，你需要求出每次修改后上述问题的答案。

[problemUrl]: https://atcoder.jp/contests/agc017/tasks/agc017_c $ N $ 個のボールが一列に並んでいます． 左から $ i $ 番目のボールには，最初整数 $ A_i $ が書かれています． すぬけ君が魔法を唱えると，これらのボールは次のようにして消滅します： - ボールがちょうど $ k $ 個あるとき，$ k $ が書かれているボールすべてが同時に消滅する． すぬけ君の目標は，魔法を何回か唱えることでボールをすべて消滅させることです． これは不可能な場合があるので，すぬけ君はできるだけ少ない個数のボールに書かれている整数を変更することで，この目標を達成できるようにしたいです． これらのボールは，書かれている整数が全部で $ M $ 回自然に変化することがわかっています． $ j $ 回目の変化においては，左から $ X_j $ 番目のボールに書かれている整数が $ Y_j $ に変わります． 各変化の後の状態で，次の変化が起こる前にすぬけ君が目標を達成しようとするとき，少なくとも何個のボールに書かれている整数を変更する必要があるかを求めてください．すぬけ君は整数の変更を十分速く行うことができるものとします．ただし，すぬけ君は実際には整数の変更を行わないことに注意してください．

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ ... $ A_N $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ : $ X_M $ $ Y_M $

$ M $ 行出力せよ． $ j $ 行目には，$ j $ 回目の変化の後で，すぬけ君が目標を達成するためには，少なくとも何個のボールに書かれている整数を変更する必要があるかを出力せよ．

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

0
1
1

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

0
1
2
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

1
0
1
2
2
3
3
3
3
2

### 制約 - $ 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 $ が成り立つ． ### Sample Explanation 1 \- $ 1 $ 回目の変化の後，ボールに書かれている整数は左のボールから順に $ 2,\ 1,\ 3,\ 4,\ 5 $ になります．この状態ですぬけ君が $ 5 $ 回魔法を唱えると，すべてのボールが消滅します．そのため，$ 0 $ 個のボールに書かれている整数を変更すればよいです． - $ 2 $ 回目の変化の後，ボールに書かれている整数は左のボールから順に $ 2,\ 5,\ 3,\ 4,\ 5 $ になります．この場合，少なくとも $ 1 $ 個のボールに書かれている整数を変更する必要があります．例えば，左から $ 5 $ 番目のボールに書かれている整数を $ 2 $ に変更した後，すぬけ君が $ 4 $ 回魔法を唱えればよいです． - $ 3 $ 回目の変化の後，ボールに書かれている整数は左のボールから順に $ 2,\ 5,\ 3,\ 4,\ 4 $ になります．この場合，少なくとも $ 1 $ 個のボールに書かれている整数を変更する必要があります．例えば，左から $ 3 $ 番目のボールに書かれている整数を $ 2 $ に変更した後，すぬけ君が $ 3 $ 回魔法を唱えればよいです．