题目描述
栅栏由 N个 1米长的小段组成，小机器人可以使用 26 种不同的颜色来涂抹，他将这些颜色由浅到深用字母 “A” 到 “Z”标号（“A” 是很浅的颜色，“Z” 是很深的颜色）。这样他就可以用一个长为 N的字符串来描述他想要给栅栏的每一小段涂上的颜色。
一开始，所有栅栏的小段都没有被涂上颜色。小机器人一笔可以给任意连续若干小段涂上同一种颜色，如果遇上了有颜色的地方，只允许更深的颜色涂抹在上面。
例如，一段长是 4 的没有被涂抹颜色的栅栏可以按照下列方式上色：
.... -> BBB. -> BBLL -> BQQL
小机器人已经知道了栅栏需要被涂抹的颜色。但由于时间紧迫，小机器人认为他可能需要放弃给栅栏上的某些连续区间上色，有q个区间可以提供给小机器人选择，每一个区间是第a段到第b段栅栏，包括a和b这两段栅栏。
小机器人想要知道在这q个区间中，将所有区间外的栅栏小段涂上指定的颜色，各需要涂抹几次。下面请你编程帮助小机器人解决这个问题。
输入
输入包括若干行。
第一行包含两个整数n, m(n<5000, m<5000)，分别代表字符串的长度为n，有m个候选区间。
第二行包含一个长为n的字符串。
接下来的m行，每行包含两个整数a和b(1<=a,b<=n)，表示一个不涂色的区间。
输出
输出包含m行，每行一个整数，代表在当前不涂色区间的情况下，最少需要涂抹的次数。
样例输入
8 2
ABBAABCB
3 6
1 4样例输出
4
3