C - Snuke and Spells 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

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

入力例 1

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

出力例 1

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

入力例 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

Score : 1000 points

Problem Statement

There are N balls in a row. Initially, the i-th ball from the left has the integer A_i written on it.

When Snuke cast a spell, the following happens:

  • Let the current number of balls be k. All the balls with k written on them disappear at the same time.

Snuke's objective is to vanish all the balls by casting the spell some number of times. This may not be possible as it is. If that is the case, he would like to modify the integers on the minimum number of balls to make his objective achievable.

By the way, the integers on these balls sometimes change by themselves. There will be M such changes. In the j-th change, the integer on the X_j-th ball from the left will change into Y_j.

After each change, find the minimum number of modifications of integers on the balls Snuke needs to make if he wishes to achieve his objective before the next change occurs. We will assume that he is quick enough in modifying integers. Here, note that he does not actually perform those necessary modifications and leaves them as they are.

Constraints

  • 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

Subscore

  • In the test set worth 500 points, N \leq 200 and M \leq 200.

Input

Input is given from Standard Input in the following format:

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

Output

Print M lines. The j-th line should contain the minimum necessary number of modifications of integers on the balls to make Snuke's objective achievable.

Sample Input 1

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

Sample Output 1

0
1
1
  • After the first change, the integers on the balls become 2, 1, 3, 4, 5, from left to right. Here, all the balls can be vanished by casting the spell five times. Thus, no modification is necessary.
  • After the second change, the integers on the balls become 2, 5, 3, 4, 5, from left to right. In this case, at least one modification must be made. One optimal solution is to modify the integer on the fifth ball from the left to 2, and cast the spell four times.
  • After the third change, the integers on the balls become 2, 5, 3, 4, 4, from left to right. Also in this case, at least one modification must be made. One optimal solution is to modify the integer on the third ball from the left to 2, and cast the spell three times.

Sample Input 2

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

Sample Output 2

0
1
2
3

Sample Input 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

Sample Output 3

1
0
1
2
2
3
3
3
3
2