P12182 DerrickLo's Brackets (UBC002E)

DerrickLo has an integer array $a$ with $n$ numbers, and a array $t$ with $n$ characters which are either `(` or `)` ($1\le n\le 10^6$, $1\le a_i\le 10^9$). Now he will generate $q$ bracket strings by selecting an interval $[l,r]$ ($1\le l\le r\le n$) and perform the following operation to a string $S$ which is initially empty. - For each integer $i$ from $l$ to $r$, append $a_i$ copies of $t_i$ to $S$. After each generation, DerrickLo wants to know the longest good substring of $S$. Please help him! A good string is defined as, - An empty string is a good string. - If $A$ is a good string, then so does $(A)$. - If $A,B$ are both good strings, then so does $AB$. - Any other strings are **not** good strings.

The first line contains two integers $n,q$. The second line contains $n$ integers representing $a$. The third line contains a string representing $t$. For the next $q$ lines, each one contains two integers representing $l,r$ for a generation.

Output $q$ lines. The $i$-th one representing the $i$-th answer.

$S$ of the first generation is `(()))(`. Its longest good substring is `(())`, so output $4$. $S$ of the second generation is `)))(`. Its longest good substring is an empty string, so output $0$.