問題文

0 以上 M 未満の整数からなる長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

Q 個のクエリが与えられるので順に処理してください。i 番目のクエリは以下で説明されます。

• 整数 x_i,y_i が与えられる。 A の x_i 番目の要素を y_i で更新する。その後、以下の問題を解け。
  • 整数列 A をもとにして頂点数 N の無向グラフ G を作る。頂点には 1,2,\ldots,N までの番号がつけられており、頂点 u,v\ (1\leq u\lt v\leq N) の間には A_u+1\equiv A_v\ (\mathrm{mod}\ M) が成り立つとき辺が張られる。 G の最大マッチングの大きさを求めよ。

制約

• 2\leq N\leq 3\times 10^5
• 1\leq Q\leq 3\times 10^5
• 2\leq M\leq 3\times 10^5
• 0\leq A_i\lt M
• 1\leq x_i\leq N
• 0\leq y_i\lt M
• 入力は全て整数

部分点

この問題には複数の部分点が設定されている。

• 追加の制約 Q=1 を満たすデータセットに正解した場合は 10 点が与えられる。
• 追加の制約 M\leq 100 を満たすデータセットに正解した場合は 10 点が与えられる。

入力例 1

6 3 5
1 1 0 2 0 2
6 0
4 1
5 2
1 2
6 2

出力例 1

1
1
2
3
3

1 つ目のクエリについて、 A_6 が 0 に更新され A=(1,1,0,2,0,0) になります。 G には頂点 1,4 の間と頂点 2,4 の間と頂点 4,5 の間と頂点 4,6 の間に辺が張られるため、G の最大マッチングの大きさは 1 です。

2 つ目のクエリについて、 A_4 が 1 に更新され A=(1,1,0,1,0,0) になります。 G には頂点 3,4 の間に辺が張られるため、G の最大マッチングの大きさは 1 です。