P12182 DerrickLo's Brackets (UBC002E)

DerrickLo 有一个长度为 $n$ 的正整数序列 $a$，以及一个长度为 $n$ 的仅含有 `(` 与 `)` 的字符序列 $t$。他现在要根据这两个序列生成 $q$ 组括号序列，具体地，他会选择两个在 $[1,n]$ 中的正整数 $l,r$ 且 $l\le r$ 并对一个初始为空的字符串 $S$ 进行如下操作： - 从小到大枚举每个在 $[l,r]$ 之间的正整数 $i$，将 $a_i$ 个 $t_i$ 加到 $S$ 的末尾。 他希望你能在每次他生成了一个括号序列 $S$ 后告诉他 $S$ 的最长合法匹配子串的大小。 合法匹配串的定义如下： - 空串是合法匹配串。 - 若 $A$ 是合法匹配串，则 $(A)$ 为合法匹配串。 - 若 $A,B$ 都是合法匹配串，则 $AB$ 为合法匹配串。 - 除此以外的所有字符串都不是合法匹配串。

无

无

**样例说明** 第一次生成的括号序列为 `(()))(`，它的最长合法匹配子串为 `(())`。 第二次生成的括号序列为 `)))(`，它的最长合法匹配子串为空串。 **数据范围** $1\le n,q\le 10^6$，$1\le a_i\le 10^9$，每次生成中的 $l,r$ 满足 $1\le l\le r\le n$，$t$ 仅由 `(` 与 `)` 组成。除 $t$ 外所有输入数据为整数。