题目描述
给你一个长度为 $n$ 的括弧序列和 $m$ 组询问，每次询问区间 $[l,r]$ 中最长合法括号子序列。 合法括号序列定义如下：
1.空序列是合法括号序列；
2.若 $S$ 是合法括号序列则 $(S)$ 是合法括号序列；
3.若 $S1$、$S2$ 是合法括号序列，则 $S1S2$ 是合法括号序列。
括弧序列定义如下：由 `(` 和 `)` 组成的序列。
输入
第一行输入两个数 $n,m$，
第二行输入一个字符串，表示括弧序列，
第 $3-m+2$ 行每行输入两个数 $l,r$ 表示区间 $l-r$。
输出
输出 $m$ 个数，每个数分别表示 $[l,r]$ 区间能选出多少个括号使得选出的括号组成的序列在 $[l,r]$ 之间能形成最长的括号序列。
样例输入输出
输入#1
复制
10 6
(()(()))()
3 5
1 7
6 8
3 7
4 5
4 10
提示
对于 $40\%$ 的数据，$n \leq 1000$，$m \leq 1000$。
对于 $100\%$ 的数据，$n \leq 400000$，$m \leq 200000$。