4156. 因你而在的故事

【题目描述】

往世乐土的数据共有 $n$ 个节点，从左到右排布成一行，编号分别为 $1 \sim n$，每个节点都存储了一个字符 $c_i$. 由于某种原因，$c_i$ 只可能是 $f$, $q$, $h$ 中的一个。

Elysia 会进行 $q$ 次询问，每次选定一个区间 $[l, r]$ 释放魔法。

魔法会使序列发生一些变化，具体地，会不断将区间中最靠左的子串 $fqh$ 改为 $hqf$，直到不能再修改。

Elysia 想知道操作后区间中子串 $hqh$ 的个数。

如果你回答不上来，往世乐土就会被侵蚀之律者入侵。为了可爱的粉色妖精小姐，还是认真想想这个问题吧……

注意每次询问之间独立。

【输入格式】

第一行一个正整数 $n$，表示数据节点数。

第二行 $n$ 个字符 $c_1, c_2, \cdots, c_n$，分别表示每个节点存储的字符。

第三行一个正整数 $q$，表示询问的个数。

以下 $q$ 行，每行两个正整数 $l, r$，意义见【题目描述】。

【输出格式】

输出共 $q$ 行。

对于 Elysia 的每次询问，输出一行一个整数，表示操作后区间中子串 $hqh$ 的个数。

【样例1输入】

8
fqhqhfqh
1
1 7

【样例1输出】

1

【样例1说明】

选择区间 $[1, 7]$ 使用魔法，将会对 $s'=c_1c_2\cdots c_7 = fqhqhfq$ 进行操作。

第一次操作会将 $s'$ 变为 $hqfqhfq$；

第二次操作会将 $s'$ 变为 $hqhqffq$.

最后 $s'$ 中只有一个子串满足题目条件。

【样例2输入】

22
fqhqhqfhqhfqhqhfqhfqhf
6
1 1
3 5
1 22
2 17
14 15
4 14

【样例2输出】

0
1
3
3
0
1

【样例3/4】

样例3/4下载

【数据规模与约定】

对于所有测试数据，$1 \le n, q \le 5 \times 10^5$，$1 \le l, r \le n$，$c_i \in \{f, q, h\}$.

特殊性质：保证字符串随机生成。

【来源】

校际联合邀请赛第6场入门组T4