Para cualquier sucesión, se dice que es "eliminable" si puede quedar vacía tras realizar un número finito de operaciones de eliminación. Una operación de eliminación se define de la siguiente manera:
- Sea $k$ la longitud actual de la sucesión, se eliminan todos los números de la sucesión que sean iguales a $k$.
Se tiene una sucesión $a$ de longitud $n$ y $m$ operaciones de modificación. Después de cada modificación $i$, debes responder: ¿cuántos números, como mínimo, se necesitan modificar en la sucesión $a$ para que sea eliminable?
Cada operación de modificación consiste en una modificación de un solo elemento, sumar uno a toda la sucesión o restar uno a toda la sucesión.
Entrada
La primera línea contiene dos enteros positivos $n$ y $m$, que representan la longitud de la sucesión y el número de modificaciones, respectivamente.
La segunda línea contiene $n$ enteros positivos que representan la sucesión $a$, donde el $i$-ésimo número de la entrada es el $i$-ésimo elemento de la sucesión $a_i$.
Las siguientes $m$ líneas contienen dos enteros $p$ y $x$, que representan una operación de modificación.
Cuando $1 \le p \le n$, la operación es una modificación de un solo elemento: cambiar el $p$-ésimo elemento de la sucesión $a_p$ por $x$.
Cuando $p = 0$, la operación consiste en sumar $x$ a toda la sucesión.
Salida
Imprime $m$ líneas, cada una con un entero, donde la $i$-ésima línea representa la respuesta después de las primeras $i$ modificaciones.
Ejemplos
Entrada 1
3 9 1 2 3 1 1 0 1 0 1 0 1 2 2 3 2 0 -1 0 -1 0 -1
Salida 1
0 1 2 3 2 1 1 2 2
Nota 1
Después de la primera modificación, la sucesión es $(1, 2, 3)$, la cual es eliminable sin necesidad de cambios.
Después de la cuarta modificación, la sucesión es $(4, 5, 6)$, se requiere cambiar los tres números para que sea eliminable.
Después de la sexta modificación, la sucesión es $(4, 2, 2)$, cambiando el primer número a $3$ la sucesión se vuelve eliminable.
Después de la novena modificación, la sucesión es $(1, -1, -1)$, se puede cambiar el segundo número a $2$ y el tercer número a $3$ para que sea eliminable.
Subtareas
| Subtarea # | Puntuación | $n \le$ | $m \le$ | ¿Satisface $p > 0$? |
|---|---|---|---|---|
| $1$ | $7$ | $5$ | $10$ | No |
| $2$ | $14$ | $300$ | $1$ | Sí |
| $3$ | $15$ | $3000$ | $1$ | Sí |
| $4$ | $11$ | $3000$ | $3000$ | Sí |
| $5$ | $13$ | $10^5$ | $10^5$ | Sí |
| $6$ | $32$ | $10^5$ | $10^5$ | No |
| $7$ | $8$ | $1.5 \times 10^5$ | $1.5 \times 10^5$ | No |
Para el $100\%$ de los datos:
- $1 \le n, m \le 1.5 \times 10^5$
- $1 \le a_i \le n$
- $0 \le p \le n$
- Cuando $p > 0$, $1 \le x \le n$.
- Cuando $p = 0$, $x = -1$ o $1$.