给定一个长度为 $n$ 的括号串 $S$ , 有 $m$ 次询问 , 每次询问区间 $[l,r]$ 中的最长子序列长度,满足是合法括号串。
括号串为只由 $($ 和 $)$ 组成的字符串。
合法括号串的定义如下:
- 空串是合法括号串
- 如果 $S$ 是合法括号串 , 那么 $(S)$ 是合法括号串
- 如果 $S$ , $T$ 是合法括号串 , 那么 $ST$ 是合法括号串
输入格式
第一行两个整数 $n,m$ , 含义如题面所示。$(1 \leq n , m \leq 10^5)$
第二行一个字符串 $S$ , 保证 $S$ 中只包含 $($ 和 $)$。
接下来 $m$ 行 , 每行两个整数 $l,r$ , 含义如题面所示。$(1 \leq l \leq r \leq n)$
输出格式
输出共 $m$ 行 , 第 $i$ 行表示第 $i$ 次询问的答案。
样例输入
10 5
))()()()))
6 10
7 8
7 7
7 8
4 9
样例输出
2
2
0
2
4