本题使用标准输入、标准输出，无需读写题面中提到的文件。

题目描述

Bessie 最近收到了一套绘画工具，她想给牧场一端的长栅栏上色。栅栏由 $N$ 段连续的 1 米长栅栏段组成（$1\le N\le 10^5$）。Bessie 有 26 种不同的颜色可用，她用字母 'A' 到 'Z' 来标记这些颜色，按颜色深浅递增排序（'A' 很浅，'Z' 很深）。因此，她可以用一个长度为 $N$ 的字符串来描述她希望每段栅栏涂成的颜色，其中每个字符是一个字母。 起初，所有栅栏段都是未上色的。只要她从不在更深的颜色上涂更浅的颜色（她只能在更浅的颜色上涂更深的颜色），她就可以在一次刷涂中把任意一段连续的栅栏段涂成同一种颜色。 例如，一段长度为四的、最初未上色的栅栏段可以按如下方式上色： .... -> BBB. -> BBLL -> BQQL 时间不够时，Bessie 认为她可能需要留下一段连续的栅栏段不涂！目前，她正在考虑 $Q$ 个候选区间（$1\le Q\le 10^5$），每个区间由两个整数 $(a,b)$ 描述，其中 $1 \leq a \leq b \leq N$，表示要保留不涂的区间端点索引，即第 $a \ldots b$ 段将保持未上色。 对于每个候选区间，在让区间内所有栅栏段保持未上色的同时，将区间外每段栅栏涂成目标颜色所需的最少刷涂次数是多少？注意，Bessie 实际上并不会在这个过程中进行涂色，因此每个候选区间的答案彼此独立。

输入格式

第一行包含 $N$ 和 $Q$。 下一行包含一个长度为 $N$ 的字符串，表示每段栅栏期望的颜色。 接下来的 $Q$ 行每行包含两个用空格分隔的整数 $a$ 和 $b$，表示一个可能要留空不涂的候选区间。

输出格式

对每个 $Q$ 个候选区间，输出对应答案，每行一个。

8 2
ABBAABCB
3 6
1 4

4
3

提示

在这个例子中，排除与目标模式 $\texttt{BAAB}$ 对应的子区间需要四次刷涂才能完成，而排除 $\texttt{ABBA}$ 则只需要三次。 .... -> AA.. -> ABBB -> ABCB SCORING: 测试点 1-4 满足 $N,Q\le 100$。 测试点 5-7 满足 $N,Q\le 5000$。 测试点 8-13 没有额外限制。 题目鸣谢：Andi Qu 和 Brian Dean

来源

USACO|2021|Silver