A sequence is called "erasable" if it can be reduced to an empty sequence through a finite number of deletion operations. A single deletion operation is defined as follows:
- Let the current length of the sequence be $k$. Delete all elements in the sequence that are equal to $k$.
Given a sequence $a$ of length $n$, there are $m$ modification operations. After each modification $i$, you must answer: what is the minimum number of elements that need to be modified in the current sequence $a$ so that it becomes erasable?
Each modification operation is either a point update, adding a value to the entire sequence, or subtracting a value from the entire sequence.
Input
The first line contains two positive integers $n$ and $m$, representing the length of the sequence and the number of modifications, respectively.
The second line contains $n$ positive integers representing the sequence $a$, where the $i$-th number is $a_i$.
The next $m$ lines each contain two integers $p$ and $x$, representing a modification operation.
When $1 \le p \le n$, the operation is a point update: change the $p$-th element $a_p$ to $x$.
When $p = 0$, the operation is to add $x$ to every element in the sequence.
Output
Output $m$ lines, each containing one integer. The $i$-th line represents the answer after the $i$-th modification.
Examples
Input 1
3 9 1 2 3 1 1 0 1 0 1 0 1 2 2 3 2 0 -1 0 -1 0 -1
Output 1
0 1 2 3 2 1 1 2 2
Note 1
After the first modification, the sequence is $(1, 2, 3)$, which is already erasable.
After the fourth modification, the sequence is $(4, 5, 6)$, and all three elements must be changed to make it erasable.
After the sixth modification, the sequence is $(4, 2, 2)$, and changing the first element to $3$ makes it erasable.
After the ninth modification, the sequence is $(1, -1, -1)$, and changing the second element to $2$ and the third element to $3$ makes it erasable.
Subtasks
| Subtask # | Score | $n \le$ | $m \le$ | Satisfies $p > 0$ |
|---|---|---|---|---|
| $1$ | $7$ | $5$ | $10$ | No |
| $2$ | $14$ | $300$ | $1$ | Yes |
| $3$ | $15$ | $3000$ | $1$ | Yes |
| $4$ | $11$ | $3000$ | $3000$ | Yes |
| $5$ | $13$ | $10^5$ | $10^5$ | Yes |
| $6$ | $32$ | $10^5$ | $10^5$ | No |
| $7$ | $8$ | $1.5 \times 10^5$ | $1.5 \times 10^5$ | No |
For $100\%$ of the data:
- $1 \le n, m \le 1.5 \times 10^5$
- $1 \le a_i \le n$
- $0 \le p \le n$
- When $p > 0$, $1 \le x \le n$.
- When $p = 0$, $x = -1$ or $1$.