Hello!

Some time ago I thought of the following problem:

We have a bracket sequence with length n (n ≤ 10⁵) and we have q (q ≤ 10⁵) queries for finding the length of the longest correct bracket substring (with consecutive elements) in a interval [l;r] (1 ≤ l ≤ r ≤ n).

Sample:

6
((()()
3
1 6 -> Answer is 4 (substring from 3rd to 6th position)
1 2 -> There is no correct bracket substring so the answer is 0
1 4 -> Answer is 2 (substring from 3rd to 4th position)

So I found a solution with MO's algorithm but I am curious if there is an online solution. So if anyone has one, please share it. Thanks in advance.