#2710. 「BalkanOI 2018 Day1」Election

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Planet6174

题目描述

翻译自 BalkanOI 2018 Day1 T1「Election

有一个长度为 N 的字符串 S[1\dots N] ,它仅由 CT 两种字母组成。
现在有 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