#P18005. Greatest Bracket Sequence
Greatest Bracket Sequence
Greatest Bracket Sequence
给定一个长度为 、仅含 ( 和 ) 的字符串 。
回答 次询问。每次给定 ,令 。可以任意选择一个正整数 ,将 个 连接起来,再从连接后的字符串中选择一个连续子串 ,要求 是合法括号序列。允许 为空串。
判断 的长度是否存在最大值。若存在,输出最大长度;否则输出 。
合法括号序列指能通过反复删除连续子串 (),最终变成空串的字符串。删除次数可以为零。
输入格式
第一行两个整数 。第二行字符串 。接下来 行,每行两个整数 。字符串下标从 开始。
输出格式
输出 行,每行给出对应询问的最大长度;若长度无上界则输出 -1。
数据范围
,。,且 只含两种括号。
样例 1
输入
4 3
()((
2 3
1 4
3 4
输出
-1
2
0