Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Straightforward

By tanu_RUET · Limits 1s, 512 MB

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 ( 1lrN ). 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. 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:
1N5×105
1Q106
1lrN

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

InputOutput
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

Discussion

Statistics


25% Solution Ratio

EgorKulikovEarliest, 3w ago

Tashdid_trdbFastest, 0.2s

Tashdid_trdbLightest, 26 MB

YouKnowWhoShortest, 1697B

Submit

Login to submit

Related Contests

Criterion 2020 Round 1 Ended at 2020-01-31 11:30:00 +0000 UTC