Straightforward

No gossip. In this problem I will just say what to do. Initially, you will be given a bracket sequence of length $N$. Then there will be some queries. In each query you will be given two integers $l$, $r$ ($1 ≤ l ≤ r ≤ N$). You will have to find the maximum length of balanced bracket substring that starts from index $l$ and ends not after index $r$. Here substring means a continious sub-part of a string.

Input

In the first line there will be an integer $N$ ($1 ≤ N ≤ 5×10^5$). Then there will be a string of length $N$ containing only characters '(' or ')'. In next line there will be an integer $Q$ ($1 ≤ Q ≤ 10^6$) indicating the number of queries. Then each of the $Q$ lines will contain two integers $l$ and $r$ ($1 ≤ l ≤ r ≤ N$) as described in statement.

Output

For each query print the maximum length of continuous bracket sequence that is balanced and starts from index $l$ and ends not after index $r$.

Sample

10
()(())())(
5
1 9
1 1
1 2
9 10
2 5

8
0
2
0
0

You can learn more about balanced bracket sequence from here.