题目名称：括号表达式

问题背景

对于一个仅由 '(' 和 ')' 组成的括号序列来说：

• 空序列是一个合法的括号表达式序列；
• 若 $s$ 是一个合法的括号表达式序列，则 $(s)$ 也是合法的括号表达式序列；
• 若 $s$ 和 $t$ 都是合法的括号表达式序列，则 $st$ 也是合法的括号表达式序列。

比如：

• "(()()())()" 是合法的括号表达式序列
• "(())((()))" 是合法的括号表达式序列
• "((()))((()()))" 是合法的括号表达式序列
• ")()(" 不是合法的括号表达式序列
• "(((()()))()" 不是合法的括号表达式序列

题目描述

给定一个长度为 $n$ 的仅由字符 '(' 和 ')' 组成的括号序列 $s_1, s_2, \ldots, s_n$。

你需要回答 $m$ 次询问，每次询问给你两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），你需要回答出序列 $s_{l_i}, s_{l_i + 1}, \ldots, s_{r_i}$ 的所有子序列中最长的合法的括号表达式序列的长度。

注：子序列可以不连续。

输入格式

输入的第一行包含一个字符串 $s_1, s_2, \ldots, s_n$，仅由字符 '(' 和 ')' 构成。（注：第一行仅一行字符串，$n(1 \le n \le 10^6)$ 没有给你，需要你自己求）

输入的第二行包含一个一个整数 $m$，表示询问次数。

接下来 $m$ 行，每行包含两个整数 $l_i$ 和 $r_i$，表示一次询问（$1 \le l_i \le r_i \le n$）。

输出格式

对于每次询问，输出一行，包含一个整数，表示 $s_{l_i}, s_{l_i+1}, \ldots, s_{r_i}$ 的子序列中最长的合法的括号表达式序列的长度。

样例

())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10

0
0
2
10
4
6
6

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n,m \le 10$
• 对于 $60\%$ 的数据，$n,m \le 1000$
• 对于 $100\%$ 的数据，$1 \le n \le 10^6, 1 \le m \le 10^5$