题目描述

翻译自 BalkanOI 2018 Day1 T1「Election」

有一个长度为 $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$。