### 问题描述 小齐想要油漆她牧场尽头的长篱笆。篱笆由 $N$ 个相邻的 $1$ 米长的小段组成。小齐有 $26$ 种不同的颜色可用，她用字母 $A$ 到 $Z$ 按颜色深浅的顺序进行标记（$A$ 是很浅的颜色，$Z$是很深的颜色）。因此，她可以将她想要为每个篱笆段着色的颜色描述为一个长度为 $N$ 的字符串，其中每个字符都是一个字母。 最初，所有篱笆段都没有颜色。小齐可以用一次笔画将任何一段连续的段涂成单一颜色，只要她不在较深的颜色上涂上较浅的颜色（她只能将较深的颜色涂在较浅的颜色上面）。 时间紧迫，小齐认为她可能需要留一些连续的篱笆段不涂色！目前，她正在考虑 $Q$ 个候选范围，每个范围由两个整数 $a$ 和 $b$ 描述，其中 $1 \leq a \leq b \leq N$ 表示要保持未着色的段的索引端点。 对于每个候选范围，要在保持范围内的所有篱笆段不着色的情况下，着色其余每个篱笆段，最少需要多少笔画？注意，小齐实际上并没有在这个过程中进行任何涂色，因此每个候选范围的答案是独立的。 ### 输入格式 第一行包含整数 $N$ 和 $Q$。 第二行包含长度为 $N$ 的字符串，表示每个篱笆段的期望颜色。 接下来的 $Q$ 行，每行包含两个用空格分隔的整数 $a$ 和 $b$，表示可能保留未涂色的范围的索引端点。 ### 输出格式 对于每个候选范围，输出一个新行，表示答案。 ### 样例输入 ``` 8 2 ABBAABCB 3 6 1 4 ``` ### 样例输出 ``` 4 3 ``` ### 评测数据规模 $1 \leq N \leq 10^5$，$1 \leq Q \leq 10^5$。