Description

Translated from BalkanOI 2018 Day 1 T1 “Election”.

There is a string $S[1\dots N]$ of length $N$, consisting only of the two letters C and T.
Now there are $Q$ queries. Each query contains two integers $L$ and $R$, meaning: let the new string be $S' = S[L\dots R]$. What is the minimum number of characters that must be deleted from $S'$ to ensure that, for every prefix and every suffix of $S'$, the number of C is not less than the number of T?

Input Format

The first line contains an integer $N$.
The second line contains a string $S$ of length $N$.
The third line contains an integer $Q$.
In the next $Q$ lines, each line contains two integers $L$ and $R$, representing one query.

Output Format

For each query, output one line: the minimum number of characters that must be deleted from $S'$ to satisfy the requirement in the statement.

11
CCCTTTTTTCC
3
1 11
4 9
1 6

4
6
3

Hint

Sample Explanation

Query 1: CCCTTTTTTCC.
Query 2: TTTTTT.
Query 3: CCCTTT.

Subtask #1 (28 points): $1 \le N, Q \le 2000$.
Subtask #2 (54 points): $1 \le N, Q \le 7 \times 10^4$.
Subtask #3 (18 points): $1 \le N, Q \le 5 \times 10^5$.

Thanks to Planet6174 for providing the translation.

Translated by ChatGPT 5