题目描述

在本题中，11/22 字符串的定义与 A 问题和 C 问题相同。

当字符串 $T$ 满足以下所有条件时，称 $T$ 为 11/22 字符串。

• $|T|$ 是奇数。这里 $|T|$ 表示 $T$ 的长度。
• 第 $1$ 个字符到第 $\frac{|T|+1}{2}-1$ 个字符均为 1。
• 第 $\frac{|T|+1}{2}$ 个字符为 /。
• 第 $\frac{|T|+1}{2}+1$ 个字符到第 $|T|$ 个字符均为 2。

例如，11/22、111/222、/ 是 11/22 字符串，而 1122、1/22、11/2222、22/11、//2/2/211 不是。

给定一个由 1、2、/ 组成的长度为 $N$ 的字符串 $S$，请处理 $Q$ 个查询。

每个查询给出 $L$、$R$，请你求出 $S$ 的第 $L$ 个字符到第 $R$ 个字符组成的连续子串中，作为 $T$ 时，11/22 字符串的**（不要求连续的）**子序列的最大长度。若不存在这样的子序列，则输出 $0$。

输入格式

输入以如下格式从标准输入读入。这里 $\mathrm{query}_i$ 表示第 $i$ 个查询。

$N$ $Q$
$S$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

每个查询的格式如下：

$L$ $R$

输出格式

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。

输入输出样例 #1

输入 #1

12 5
111/212/1122
1 7
9 12
3 6
4 10
1 12

输出 #1

5
0
3
1
7

说明/提示

约束

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $S$ 是由 1、2、/ 组成的长度为 $N$ 的字符串
• $1 \leq L \leq R \leq N$
• $N, Q, L, R$ 均为整数

样例解释 1

对于第 $1$ 个查询，$S$ 的第 $1$ 个字符到第 $7$ 个字符组成的子串为 111/212。该字符串包含 11/22 作为子序列，这是 11/22 字符串中长度最大的。因此答案为 $5$。对于第 $2$ 个查询，$S$ 的第 $9$ 个字符到第 $12$ 个字符组成的子串为 1122。该字符串不包含任何 11/22 字符串作为子序列，因此答案为 $0$。

由 ChatGPT 4.1 翻译