[BalkanOI2018] Election

**翻译自 [BalkanOI 2018](http://boi2018.ro) Day1 T1「[Election](http://boi2018.ro/assets/Tasks/BOI/Day_1/election/elections_en.pdf)」** 有一个长度为 $N$ 的字符串 $S[1\dots N]$，它仅由 `C` 和 `T` 两种字母组成。 现在有 $Q$ 个查询，每个查询包含两个整数 $L$ 和 $R$，表示：设新字符串 $S'=S[L\dots R]$，至少在 $S'$ 中要删除多少个字符，才能保证：对于 $S'$ 的每一个前缀和后缀，其 `C` 的数量都不小于 `T` 的数量。

第一行有一个整数 $N$。 第二行有一个长度为 $N$ 的字符串 $S$。 第三行有一个整数 $Q$。 在接下来的 $Q$ 行中，每行有两个整数 $L$ 和 $R$，表示一组查询。

对于每组查询输出一行，表示至少在 $S'$ 中要删除多少个字符，才能保证题面要求。

11
CCCTTTTTTCC
3
1 11
4 9
1 6

4
6
3

#### 样例解释 查询 1：`CCCTTTTTTCC`； 查询 2：`TTTTTT`； 查询 3：`CCCTTT`。 子任务 #1（28 分）：$1 ≤ N, Q ≤ 2000$； 子任务 #2（54 分）：$1 ≤ N, Q ≤ 7\times 10^4$； 子任务 #3（18 分）： $1 ≤ N, Q ≤ 5\times 10^5$。 感谢 Planet6174 提供的翻译