AT_utpc2025_g.Greatest Bracket Sequence

本题的设定与 F 问题相同。

给定一个仅由 ( 和 ) 组成、长度为 $N$ 的字符串 $S$。

请你回答 $Q$ 个询问。对于第 $i$ 个询问，会给出两个整数 $L_i, R_i$，请解决以下问题。

考虑 $S$ 的第 $L_i$ 个字符到第 $R_i$ 个字符所形成的子字符串 $X$。

选择一个正整数 $k$，再从 $X$ 重复连接 $k$ 次得到的字符串中，选择一个子串 $Y$。这里要求 $Y$ 必须是一个「正确括号序列」。$Y$ 可以为空串。

判定 $Y$ 的长度的最大可能值是否存在，如果存在请输出最大值。

「正确括号序列」指的是，可以通过若干次（可为 $0$ 次）删除子串 () 变成空字符串的字符串。

输入通过标准输入给出，格式如下：

$N\ Q\ S\ L_1\ R_1\ L_2\ R_2\ \vdots\ L_Q\ R_Q$

请输出 $Q$ 行。第 $i$ 行对于第 $i$ 个询问，如果 $Y$ 的最大可能长度存在，则输出该最大值，否则输出 -1。

样例解释 1

对于第 $1$ 个询问，$X = )($。对于任意正整数 $k$，从 $X$ 重复 $k$ 次得到的字符串中，去掉开头和结尾的字符所得到的长度为 $2k-2$ 的子串都是正确括号序列，因此 $Y$ 的最大长度不存在上限。

对于第 $2$ 个询问，$X = ()(( $。可以证明 $Y$ 的长度最大可能为 $2$。

对于第 $3$ 个询问，$X = ( ($。最大可能长度为 $0$。注意 $Y$ 可以为空字符串。

数据范围

• $N, Q, L_i, R_i$ 均为整数
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $S$ 为仅由 ( 和 ) 组成的长度为 $N$ 的字符串
• $1 \leq L_i \leq R_i \leq N$

由 ChatGPT 5 翻译