對於任意一個數列，如果能在有限次進行下列刪數操作後將其刪為空數列，則稱這個數列可以刪空。一次刪數操作定義如下：

• 記當前數列長度為 $k$，則刪掉數列中所有等於 $k$ 的數。

現有一個長度為 $n$ 的數列 $a$，有 $m$ 次修改操作，第 $i$ 次修改後你要回答：經過 $i$ 次修改後的數列 $a$，至少還需要修改幾個數才可刪空？

每次修改操作為單點修改、數列整體加一或數列整體減一。

輸入格式

第一行兩個正整數 $n, m$，分別表示數列長度、修改次數。

第二行有 $n$ 個正整數，表示數列 $a$，即輸入的第 $i$ 個數表示數列 $a$ 的第 $i$ 個數 $a_i$。

接下來 $m$ 行，每行兩個整數 $p, x$，表示一次修改操作。

當 $1 \le p \le n$ 時，該操作為單點修改，將數列中第 $p$ 個數 $a_p$ 修改為 $x$。

當 $p = 0$ 時，該操作為數列整體加 $x$。

輸出格式

輸出 $m$ 行，每行一個整數，第 $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, 5, 6)$，需要將三個數都改掉才可能刪空。

第六次修改後，數列為 $(4, 2, 2)$，將第一個數改成 $3$ 即可刪空。

第九次修改後，數列為 $(1, -1, -1)$，可以將第二個數改成 $2$、第三個數改成 $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$。