Besi recently received a set of paints and she wants to paint a long hedge on one side of her pasture. The fence consists of N consecutive 1-meter segments (1≤N≤10
5). Besi has paints in 26 different colors, which she labeled with letters from 'A' to Z' in ascending order of darkness ('A' is the lightest color, 'Z' is the darkest). Therefore, it can describe the coloring of the hedge as a string of N characters (where each character is one of - from 'A' to Z').
Initially, all segments of the fence are not painted. Besi can paint any continuous range of segments with a single color with a single brush stroke, and she never paints a lighter over a darker one (she can paint a darker over a lighter one).
For example, she can color an initially unpainted segment of length 4 like this:
.... -> BBB. -> BBLL-> BQQL
Limited in time, Besi may leave some consecutive segments unpainted. She is now looking at Q line segment candidates (1≤Q≤10
5), each given by two integers (a,b) (1≤a≤b≤N) indicating the indexes of the segment endpoints that should stay unpainted.
For each candidate, specify the minimum number of touches required to color all segments outside that range with the desired color, leaving segments inside the range uncolored. Note that Besi doesn't actually color anything, so the answers for each candidate range are independent.
Input
The first line contains N and Q.
The next line contains N representing the desired color for each hedge segment.
Each of the next Q lines contains two space-separated integers a and b representing a range of segments that may not be colored.
Imprint
For each of the Q candidates print the answer on a new line.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
8 2
ABBAABCB
3 6
14
|
4
3 |
In this example, the range exclusion matches the desired pattern. In this example, the BAAB range exclusion requires four touches to colorize, while the ABBA range exclusion requires only three.
.... -> AA.. -> ABBB-> ABCB |