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.
In the first line there will be an integer N. Then there will be a string of length N containing only characters ‘(’ or ‘)’. In next line there will be an integer Q indicating the number of queries. Then each of the Q lines will contain two integers l and r as described in statement.Constraints:1 ≤ N ≤ 5×1051 ≤ Q ≤ 1061 ≤ l ≤ r ≤ N
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.
10 ()(())())( 5 1 9 1 1 1 2 9 10 2 5
8 0 2 0 0
If you don’t know about balanced bracket sequence, learn it from here