Pour toute suite, on dit qu'elle est « effaçable » si elle peut être réduite à une suite vide après un nombre fini d'opérations de suppression. Une opération de suppression est définie comme suit :
- Soit $k$ la longueur actuelle de la suite, on supprime tous les éléments de la suite égaux à $k$.
On dispose d'une suite $a$ de longueur $n$ et de $m$ opérations de modification. Après chaque modification $i$, vous devez répondre à la question suivante : combien d'éléments au minimum faut-il encore modifier dans la suite $a$ pour qu'elle devienne effaçable ?
Chaque opération de modification consiste soit à modifier un élément unique, soit à ajouter une valeur à tous les éléments de la suite, soit à soustraire une valeur à tous les éléments de la suite.
Entrée
La première ligne contient deux entiers positifs $n$ et $m$, représentant respectivement la longueur de la suite et le nombre de modifications.
La deuxième ligne contient $n$ entiers positifs représentant la suite $a$, où le $i$-ème nombre est $a_i$.
Les $m$ lignes suivantes contiennent chacune deux entiers $p$ et $x$, représentant une opération de modification.
Lorsque $1\le p \le n$, l'opération est une modification ponctuelle : le $p$-ème élément de la suite $a_p$ est remplacé par $x$.
Lorsque $p=0$, l'opération consiste à ajouter $x$ à tous les éléments de la suite.
Sortie
Affichez $m$ lignes, chacune contenant un entier, où la $i$-ème ligne représente la réponse après les $i$ premières modifications.
Exemples
Entrée 1
3 9 1 2 3 1 1 0 1 0 1 0 1 2 2 3 2 0 -1 0 -1 0 -1
Sortie 1
0 1 2 3 2 1 1 2 2
Remarque 1
Après la première modification, la suite est $(1, 2, 3)$, elle est déjà effaçable sans modification supplémentaire.
Après la quatrième modification, la suite est $(4, 5, 6)$, il faut modifier les trois éléments pour qu'elle devienne effaçable.
Après la sixième modification, la suite est $(4, 2, 2)$, il suffit de modifier le premier élément en $3$ pour qu'elle devienne effaçable.
Après la neuvième modification, la suite est $(1, -1, -1)$, on peut modifier le deuxième élément en $2$ et le troisième en $3$ pour qu'elle devienne effaçable.
Sous-tâches
| Sous-tâche # | Points | $n\le$ | $m\le$ | $p>0$ satisfait |
|---|---|---|---|---|
| $1$ | $7$ | $5$ | $10$ | Non |
| $2$ | $14$ | $300$ | $1$ | Oui |
| $3$ | $15$ | $3000$ | $1$ | Oui |
| $4$ | $11$ | $3000$ | $3000$ | Oui |
| $5$ | $13$ | $10^5$ | $10^5$ | Oui |
| $6$ | $32$ | $10^5$ | $10^5$ | Non |
| $7$ | $8$ | $1.5 \times 10^5$ | $1.5 \times 10^5$ | Non |
Pour $100\%$ des données :
- $1\le n,m \le 1.5 \times 10^5$
- $1\le a_i \le n$
- $0\le p\le n$
- Si $p>0$, alors $1\le x \le n$.
- Si $p=0$, alors $x=-1$ ou $1$.