Description

这是一道交互题。

如果一个字符串从正反两个方向读都相同，则称其为回文串。形式化地说，长度为 $n$ 的字符串 $s$ 是回文串当且仅当对所有 $1 \le i \le n$ 都有 $s_i = s_{n-i+1}$。例如，字符串 gg、ara、abacaba 和 rotator 是回文串，而 array、palindrome 和 uoi 不是。

我们称一个字符串为近回文串，如果可以通过重新排列其字符使其成为回文串。例如，字符串 n、ara、arr 和 array 是近回文串，而 palindrome、uoi 和 random 不是。

字符串的子串是指通过从开头和结尾删除若干（可能为零）个字符后得到的字符串。

定义 $f(s)$ 为字符串 $s$ 的所有非近回文串子串中的最大长度，若不存在这样的子串则返回 $0$。

给定一个由小写拉丁字母组成的长度为 $n$ 的字符串 $s$，以及 $q$ 个形如 $l_i$, $r_i$ 的查询。对于每个查询，计算 $f(s[l_i..r_i])$ 的值，其中 $s[l_i..r_i]$ 表示由字符 $s_{l_i}, s_{l_{i} + 1}, \ldots, s_{r_i}$ 组成的子串。

Input Format

第一行包含一个整数 $n$（$1 \le n \le 2\cdot 10^5$）——字符串的长度。

第二行包含一个由 $n$ 个小写拉丁字母组成的字符串 $s$。

第三行包含一个整数 $q$（$1 \le q \le 2\cdot 10^5$）——查询的数量。

第四行包含两个整数 $l_1, r_1$（$1 \leq l_1 \leq r_1 \leq n$）——第一个查询的参数。

后续查询的参数将由评测程序给出（见交互协议部分）。

交互协议

评测程序将从第二个查询开始，逐行输出每个查询的两个整数 $l_i$, $r_i$（$1 \le l_i \le r_i \le n$）。

评测程序在读取到你的程序对前一个查询的响应后，才会输出下一个查询的参数。

请确保在每次输出后调用刷新函数。可以使用以下方法：

• C++：fflush(stdout)、cout << endl 或 cout.flush()；
• Java：System.out.flush()；
• Pascal：flush(output)；
• Python：sys.stdout.flush()；
• 其他编程语言请参考相关文档。

Output Format

对于每个查询，输出一行一个整数——$f(s[l_i..r_i])$ 的值。

8
aabaaaba
3
3 7
1 8
4 4

4
6
0

Hint

在第一个样例中，需要回答三个查询：

1. $s[3..7] =\;$baaab，其子串 aaab 长度为 4，不是近回文串；
2. $s[1..8] =\;$aabaaaba，其子串 aabaaa 长度为 6，不是近回文串；
3. $s[4..4] =\;$a，其所有子串都是近回文串。

评分标准

• （$6$ 分）：$q=1$，$l_1=1$，$r_1=n$，$n$ 为偶数，$s$ 形如 aabbaabbaa...；
• （$9$ 分）：$q=1$，$l_1=1$，$r_1=n$，$n \le 200$；
• （$5$ 分）：$q=1$，$l_1=1$，$r_1=n$，$n \le 5000$；
• （$8$ 分）：$q=1$，$l_1=1$，$r_1=n$；
• （$10$ 分）：$s$ 仅包含字母 a 和 b；
• （$8$ 分）：对所有 $1 \le i \le q$，$s_{l_i} \neq s_{r_i}$；
• （$7$ 分）：对所有 $1 \le i < n$，$s_i \neq s_{i+1}$；
• （$10$ 分）：$s$ 仅包含字母 a、b、c、d、e 和 f；
• （$18$ 分）：对所有 $1 \le i \le q$，$(r_i-l_i+1)$ 为奇数；
• （$19$ 分）：无额外限制。

翻译由 DeepSeek V3 完成