Painting the Fence

Bessie has a fence with N segments. Each segment is 1 meter long and initially uncolored. Bessie wants to paint parts of the fence according to a desired color string of length N. The string consists of uppercase letters from 'A' to 'Z', where 'A' represents the lightest shade and 'Z' the darkest. She may paint any contiguous set of segments in one brush stroke using a single color, but she cannot paint a lighter color over a darker one (she may only darken an already painted segment).

Because she is in a hurry, Bessie considers leaving one contiguous interval unpainted. In particular, she is considering Q candidate intervals. Each candidate is defined by two integers, a and b (with 1 ≤ a ≤ b ≤ N), meaning that segments from positions a to b will remain uncolored. For every candidate interval, Bessie will paint the remaining parts of the fence (segments 1 to a−1 and segments b+1 to N) so that they match the desired colors, and she wants to do so with the minimum number of brush strokes. Each candidate is considered independently.

It is known that when painting a contiguous segment from an uncolored state, the minimum number of brush strokes needed can be computed using a greedy algorithm that maintains a monotonically increasing stack. In this algorithm, for each segment’s desired color, Bessie pops from the stack until the top is not greater than the current color, and she pushes the current color if it is not equal to the top of the stack. The number of pushes is exactly the minimal strokes needed.

Your task is to answer each candidate query by computing the sum of the minimal strokes required for the left interval (segments 1 to a−1) and for the right interval (segments b+1 to N).

inputFormat

The first line contains two integers N and Q (1 ≤ N, Q ≤ 10⁵).

The second line contains a string S of length N consisting of uppercase letters 'A' to 'Z', representing the desired colors for the fence segments.

Each of the next Q lines contains two integers a and b (1 ≤ a ≤ b ≤ N), defining the candidate interval that Bessie will leave unpainted.

outputFormat

For each candidate query, output one integer on a new line representing the minimum number of brush strokes required to paint the segments outside the candidate interval.

sample

8 3
BQQLBQQL
2 5
1 3
4 8

3
4
2