配点 : $1000$ 点

問題文

$N$ 個のボールが一列に並んでいます． 左から $i$ 番目のボールには，最初整数 $A_i$ が書かれています．

すぬけ君が魔法を唱えると，これらのボールは次のようにして消滅します：

• ボールがちょうど $k$ 個あるとき，$k$ が書かれているボールすべてが同時に消滅する．

すぬけ君の目標は，魔法を何回か唱えることでボールをすべて消滅させることです． これは不可能な場合があるので，すぬけ君はできるだけ少ない個数のボールに書かれている整数を変更することで，この目標を達成できるようにしたいです．

これらのボールは，書かれている整数が全部で $M$ 回自然に変化することがわかっています． $j$ 回目の変化においては，左から $X_j$ 番目のボールに書かれている整数が $Y_j$ に変わります．

各変化の後の状態で，次の変化が起こる前にすぬけ君が目標を達成しようとするとき，少なくとも何個のボールに書かれている整数を変更する必要があるかを求めてください．すぬけ君は整数の変更を十分速く行うことができるものとします．ただし，すぬけ君は実際には整数の変更を行わないことに注意してください．

制約

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

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

0
1
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$ 回魔法を唱えればよいです．

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