P4786 [BalkanOI 2018] Election

**Translated from [BalkanOI 2018](http://boi2018.ro) Day 1 T1 “[Election](http://boi2018.ro/assets/Tasks/BOI/Day_1/election/elections_en.pdf)”.** 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`?

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.

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

#### 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