当前没有测试数据。

5.括号匹配

题目描述

给你一个长度为$n$的括弧序列和$m$组询问，每次询问区间$[l，r]$中最长合法括号子序列。合法括号序列定义如下：

1. 空序列是合法括号序列；
2. 若$S$是合法括号序列则$"($S$)"$是合法括号序列；
3. 若$S_1$、$S_2$是合法括号序列，则$"S_1S_2"$是合法括号序列。

括弧序列定义如下：由$“(”$和$“)”$组成的序列。

输入格式

第一行输入两个数$n$，$m$；

第二行输入一个字符串，表示括弧序列；

第$3$-$m+2$行每行输入两个数$l$，$r$表示区间$l$-$r$。

输出格式

输出$m$个数，每个数分别表示$[l，r]$区间能选出多少个括号使得选出的括号组成的序列在$[l，r]$之间能形成最长的括号序列。

数据范围与提示

• 对于$40\%$的数据，$n < 1000$，$m < 1000$；
• 对于$100\%$的数据，$n \leq 400000$，$m \leq 200000$。

样例

10 6
(()(()))()
3 5
1 7
6 8
3 7
4 5
4 10

0
6
0
4
0
6