Vous jouez à un jeu de puzzle comportant $n$ pierres précieuses alignées, numérotées de $1$ à $n$ de gauche à droite. La $i$-ième pierre précieuse a pour couleur $c[i]$.
À tout moment, vous pouvez sélectionner deux pierres précieuses adjacentes de la même couleur et les supprimer. Ensuite, les pierres précieuses situées de chaque côté se rapprochent pour combler l'espace, créant potentiellement de nouvelles paires adjacentes.
On vous donne $q$ scénarios indépendants. Dans le $j$-ième scénario, vous ne considérez que les pierres précieuses allant de la pierre $l[j]$ à la pierre $r[j]$. En supposant que vous effectuiez une séquence optimale de suppressions, quel est le nombre minimum de pierres précieuses pouvant rester ?
Entrée
Votre programme doit lire depuis l'entrée standard.
La première ligne de l'entrée contient deux entiers séparés par un espace, $n$ et $q$.
La deuxième ligne de l'entrée contient $n$ entiers séparés par des espaces, $c[1], c[2], \dots, c[n]$.
Les $q$ lignes suivantes de l'entrée contiennent chacune deux entiers séparés par un espace. La $i$-ième de ces lignes contient $l[i]$ et $r[i]$.
Sortie
Votre programme doit écrire sur la sortie standard.
La sortie doit contenir $q$ lignes. La $i$-ième de ces lignes doit contenir un entier, la réponse au $i$-ième scénario.
Contraintes
Pour tous les cas de test, l'entrée respecte les bornes suivantes :
- $1 \le n \le 10^6$
- $1 \le q \le 500\,000$
- $1 \le c[i] \le 10^9$ pour tout $1 \le i \le n$
- $1 \le l[j] \le r[j] \le n$ pour tout $1 \le j \le q$
Votre programme sera testé sur des instances d'entrée respectant les restrictions suivantes :
| Sous-tâche | Score | Contraintes supplémentaires |
|---|---|---|
| 0 | 0 | Cas de test d'exemple |
| 1 | 2 | $c[1] = c[2] = \dots = c[n]$ |
| 2 | 5 | Les pierres de même couleur forment un sous-tableau contigu (Si $c[i] = c[j]$ et $i < j$, alors $c[i] = c[i + 1] = \dots = c[j]$) |
| 3 | 9 | $n, q \le 2000$ |
| 4 | 4 | $l[j] = 1$ pour tout $1 \le j \le q$ |
| 5 | 8 | Il y a exactement deux pierres précieuses de chaque couleur |
| 6 | 16 | $c[i] \le 2$ pour tout $1 \le i \le n$ |
| 7 | 18 | $n, q \le 100\,000$ |
| 8 | 15 | $n, q \le 300\,000$ |
| 9 | 23 | Aucune contrainte supplémentaire |
Exemples
Entrée 1
8 4 3 3 3 2 2 3 4 7 1 3 3 6 1 7 5 8
Sortie 1
1 0 1 4
Remarque 1
Ce cas de test est valide pour les sous-tâches 3, 7, 8 et 9.
Explication de l'exemple 1
Les $n = 8$ pierres précieuses sont représentées dans le diagramme ci-dessous.
Dans le premier scénario, seules les trois premières pierres précieuses doivent être considérées. La suppression de deux pierres adjacentes quelconques en laissera exactement une, après quoi il est impossible de supprimer davantage de pierres. Par conséquent, la réponse est 1.
Dans le deuxième scénario, les pierres précieuses peuvent être supprimées de la manière suivante, n'en laissant aucune :
Dans le troisième scénario, les pierres précieuses peuvent être supprimées de la manière suivante, en laissant une pierre :
Dans le quatrième scénario, aucune pierre précieuse ne peut être supprimée. Par conséquent, la réponse est 4.
Exemples
Entrée 2
6 3 2 1 1 2 2 1 1 6 1 4 3 6
Sortie 2
2 0 0
Remarque 2
Ce cas de test est valide pour les sous-tâches 3, 6, 7, 8 et 9.