Description

Bessie recently received a set of paints, and she wants to paint the fence at one end of her pasture. The fence consists of $N$ small segments, each 1 meter long ($1 \le N \le 10^5$). Bessie can use 26 different colors, labeled from 'A' to 'Z' from lighter to darker ('A' is very light, 'Z' is very dark). Therefore, she can describe her desired final coloring of the fence using a string of length $N$, where each character is a letter representing the color for that segment.

Initially, all fence segments are unpainted. In one brush stroke, Bessie can paint any number of consecutive segments with the same color, as long as she does not paint a lighter color over a darker color (she may only cover lighter colors with darker colors).

For example, a length 4 unpainted fence can be painted as follows:

.... -> BBB. -> BBLL -> BQQL

Because time is tight, Bessie thinks she may need to give up painting some continuous interval of the fence. She is now considering $Q$ candidate intervals ($1 \le Q \le 10^5$). Each interval is given by two integers $(a, b)$ satisfying $1 \le a \le b \le N$, representing the endpoints of the segment range $a \ldots b$ that will be left unpainted.

For each candidate interval, paint all fence segments outside the interval to the desired colors, and leave all segments inside the interval unpainted. What is the minimum number of brush strokes required? Note that Bessie does not actually perform any painting during this process, so the answers for different candidate intervals are independent.

Input Format

The first line contains $N$ and $Q$.

The next line contains a string of length $N$, representing the desired color for each fence segment.

The following $Q$ lines each contain two space-separated integers $a$ and $b$, describing a candidate interval to leave unpainted.

Output Format

For each of the $Q$ candidate intervals, output one line containing the answer.

8 2
ABBAABCB
3 6
1 4

4
3

Hint

In the sample, excluding the interval corresponding to the target colors BAAB requires 4 strokes, while excluding ABBA requires only 3 strokes.

.... -> AA.. -> ABBB -> ABCB

Test Point Properties:

• Test points 1-4 satisfy $N, Q \le 100$.
• Test points 5-7 satisfy $N, Q \le 5000$.
• Test points 8-13 have no additional constraints.

Problem by: Andi Qu, Brian Dean

Translated by ChatGPT 5