配点 : 100 点
問題文
本题的设定是 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, 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
入力
输入是按以下格式从标准输入给出的。
N Q S L_1 R_1 L_2 R_2 \vdots L_Q R_Q
出力
Q 线输出。i 行中,i 个查询,Y 如果作为长度可能存在的最大值存在,则为该最大值,如果不存在则为 -1 。
入力例 1
4 3 ()(( 2 3 1 4 3 4
出力例 1
-1 2 0
1 个查询中,X = )( 。任意正整数 k ,
您可以获得X 该值应乘以 k 从回连结的字符串中删除第一个和最后一个字符所得到的长度 2k-2 的字符串是正确的括号序列,因此,Y 可能的最大长度不存在。
2 个查询中,X = ()(( 。Y 可能的最大长度
可以证明为 2 。
请注意,
3 个查询中,X = (( 。Y 可能的最大长度
可以证明为 0 。Y 也可以是空字符串。