Elections

Time limit2sMemory limit256 MB

Summary

For each range [L, R] of a C/T vote string, find the fewest votes to nullify so Cap is never behind Tony in either forward or backward counting.

Level: Medium7 of 10
Topics: String, Prefix sum, Greedy
Solved: No attempts yet

Problem

Today we must decide which superhero team is the best: Team Cap or Team Iron Man (Tony). There are $N$ enraged fans, and each one must vote for a favorite team: 'C' (Cap) or 'T' (Tony).

Cap has no chance of winning, and he is an honest man, so he decides to commit election fraud. He wants to nullify the minimum number of votes.

The votes are counted twice:

In increasing order of fan index, skipping nullified votes.
In decreasing order of fan index, skipping nullified votes.

Cap is happy if he is never behind Tony at any point during the counting. A tie is fine, but he must never have fewer votes.

No one can interfere with Tony. He knows Cap's plan, and for $Q$ scenarios he wants to know how many votes Cap will nullify. Each scenario is given by $L$ and $R$ , and only the fans with indices from $L$ to $R$ (inclusive) take part in the vote.

Input

The first line contains $N$ , the number of fans. The second line contains a string of $N$ characters, each 'C' or 'T', giving the vote of each fan. The third line contains $Q$ , the number of scenarios. Each of the next $Q$ lines contains two integers $L$ and $R$ ( $1 \le L \le R \le N$ ).

Output

Print $Q$ lines. The $i$ -th line contains the answer for the $i$ -th scenario.

Hints

In the first scenario, the votes are CCCTTTTTTCC. The only solution is to nullify 4 of Tony's votes.

In the second scenario, the votes are TTTTTT. The only solution is to nullify all votes.

In the third scenario, the votes are CCCTTT. The only solution is to nullify all of Tony's votes.

Examples1

Example 1
Input
```
11
CCCTTTTTTCC
3
1 11
4 9
1 6
```
Expected output
```
4
6
3
```