Bessie a récemment reçu un nécessaire de peinture et veut peindre la longue clôture à une extrémité de son pâturage. La clôture comporte $N$ segments consécutifs de 1 mètre ($1\le N\le 10^5$). Bessie dispose de 26 couleurs différentes, qu'elle désigne par les lettres 'A' à 'Z' par ordre croissant d'obscurité ('A' est très clair, 'Z' très sombre). Elle peut donc décrire la couleur souhaitée de chaque segment par une chaîne de longueur $N$ dont chaque caractère est une lettre.

Initialement, tous les segments sont sans couleur. Bessie peut peindre toute plage contiguë de segments d'une seule couleur en un seul coup de pinceau, à condition de ne jamais appliquer une couleur plus claire sur une couleur plus sombre (elle ne peut appliquer que des couleurs plus sombres sur des couleurs plus claires).

Par exemple, un segment initialement sans couleur de longueur quatre peut être peint ainsi :

.... -> BBB. -> BBLL -> BQQL

Manquant de temps, Bessie pense devoir peut-être laisser une plage consécutive de segments sans peinture ! Elle envisage actuellement $Q$ plages candidates ($1\le Q\le 10^5$), chacune décrite par deux entiers $(a,b)$ avec $1 \leq a \leq b \leq N$, donnant les indices des extrémités de la plage $a \ldots b$ à laisser sans peinture.

Pour chaque plage candidate, quel est le nombre minimal de coups de pinceau nécessaires pour peindre chaque segment extérieur à la plage dans sa couleur souhaitée, tout en laissant tous les segments intérieurs sans couleur ? Bessie ne peint réellement rien pendant ce processus : les réponses pour chaque plage candidate sont donc indépendantes.

Entrée

La première ligne contient $N$ et $Q$.

La ligne suivante contient une chaîne de longueur $N$ représentant la couleur souhaitée de chaque segment de clôture.

Chacune des $Q$ lignes suivantes contient deux entiers $a$ et $b$ séparés par un espace, représentant une plage candidate à laisser éventuellement sans peinture.

Sortie

Pour chacun des $Q$ candidats, affichez la réponse sur une nouvelle ligne.

Exemples

Entrée 1

8 2
ABBAABCB
3 6
1 4

Sortie 1

4
3

Remarque

Dans cet exemple, exclure la sous-plage correspondant au motif souhaité $\texttt{BAAB}$ nécessite quatre coups de pinceau, tandis qu'exclure $\texttt{ABBA}$ n'en nécessite que trois.

.... -> AA.. -> ABBB -> ABCB

Sous-tâches

• Les tests 1–4 satisfont $N,Q\le 100$.
• Les tests 5–7 satisfont $N,Q\le 5000$.
• Les tests 8–13 n'ont aucune contrainte supplémentaire.

Auteurs du problème : Andi Qu et Brian Dean