任意の数列に対し、有限回の以下の削除操作を行って空数列にできる場合、その数列は「削除可能」であると呼ぶ。1回の削除操作は以下のように定義される。

• 現在の数列の長さを $k$ とすると、数列中の $k$ と等しい値をすべて削除する。

長さ $n$ の数列 $a$ が与えられる。$m$ 回の更新操作があり、各 $i$ 回目の更新後に以下を回答せよ：$i$ 回の更新後の数列 $a$ において、削除可能にするために変更する必要がある最小の要素数はいくつか？

各更新操作は、単一要素の変更、数列全体への 1 の加算、または数列全体からの 1 の減算のいずれかである。

入力

1行目に2つの正整数 $n, m$ が与えられる。それぞれ数列の長さと更新回数を表す。

2行目に $n$ 個の正整数が与えられる。これは数列 $a$ を表し、$i$ 番目の数は数列 $a$ の第 $i$ 要素 $a_i$ である。

続く $m$ 行の各行に2つの整数 $p, x$ が与えられ、1回の更新操作を表す。

$1 \le p \le n$ のとき、これは単一要素の変更であり、数列の第 $p$ 要素 $a_p$ を $x$ に変更する。

$p = 0$ のとき、これは数列全体への $x$ の加算である。

出力

$m$ 行出力せよ。各行に整数を1つ出力し、$i$ 行目には $i$ 回の更新後の答えを表示すること。

入出力例

入力 1

3 9
1 2 3
1 1
0 1
0 1
0 1
2 2
3 2
0 -1
0 -1
0 -1

出力 1

0
1
2
3
2
1
1
2
2

注記

1回目の更新後、数列は $(1, 2, 3)$ であり、変更なしで削除可能である。

4回目の更新後、数列は $(4, 5, 6)$ であり、削除可能にするには3つの要素すべてを変更する必要がある。

6回目の更新後、数列は $(4, 2, 2)$ であり、最初の要素を $3$ に変更すれば削除可能となる。

9回目の更新後、数列は $(1, -1, -1)$ であり、2番目の要素を $2$ に、3番目の要素を $3$ に変更することで削除可能となる。

小課題

$100\%$ のデータにおいて、

• $1 \le n, m \le 1.5 \times 10^5$
• $1 \le a_i \le n$
• $0 \le p \le n$
  • $p > 0$ のとき、$1 \le x \le n$。
  • $p = 0$ のとき、$x = -1$ または $1$。