String Folding (Hard)

Time limit1.5sMemory limit1024 MB

Summary

Given a string and many queries (l, r), find the maximum number of equal-letter pairs that touch when the substring S[l..r] is folded once between two adjacent characters.

Level: Medium6 of 10
Topics: String, Prefix sum, Dynamic programming
Solved: No attempts yet

Problem

A long strip of paper has a string of uppercase English letters written on it in a single line. For example, suppose the paper has “ABAACA” written on it, as shown in the figure below.

You fold this paper exactly once. The paper can only be folded between two adjacent characters. For example, you can fold the paper between the 4th and 5th characters, as shown below.

Among the pairs of characters that touch after folding, the number of pairs with the same character is the score of that fold. For example, the score of the fold above is $1$ . However, folding the paper between the 3rd and 4th characters, as shown below, gives a score of $2$ .

You are given a string $S$ of uppercase letters, and you must answer $Q$ queries of the following form.

$l \ r$ : If the $l$ th character, the $(l+1)$ th character, $\cdots$ , the $r$ th character are written on the paper in that order, what is the maximum score you can get by folding the paper once?

Input

The first line contains the integer $N$ , the length of the string.

The second line contains the string $S$ , which consists only of uppercase English letters.

The third line contains the integer $Q$ .

From the fourth line onward, the next $Q$ lines each contain two integers $l$ and $r$ , separated by a space, describing one query.

Output

For each query, print the answer on its own line, in order.

Constraints

$2 \le N \le 5{,}000$
$1 \le Q \le 200{,}000$
$1 \le l \lt r \le N$

Examples2

Example 1
Input
```
6
ABAACA
4
1 4
2 5
3 6
1 6
```
Expected output
```
1
1
1
2
```
Example 2
Input
```
5
ABBAB
4
1 5
1 4
2 5
3 5
```
Expected output
```
2
2
1
0
```