Bracket removal

View as PDF

Submit solution

Points: 0.30 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

A string of characters is called a bracket sequence if there exists only the characters '(' and ')' in the string.

A bracket sequence ~X~ is called simple if either:

  • ~X~ is "()",

  • ~X~ takes the form "(Y)", where ~Y~ is a simple bracket sequence.

For example, the bracket sequences (), (()) and (((()))) are simple, whereas ()(), )(, (())() or (()()) are not.

Consider a bracket sequence ~S~. We can perform the following operation on string ~S~: erase any substring of ~S~ that is a simple bracket sequence, concatenating the rest. Let us denote the complexity of string ~S~ being the least number of operations needed to perform on string ~S~, such that the string does not contain any more substrings that are simple bracket sequences.

Given a bracket sequence ~P~ of length ~n~, and ~q~ queries, the ~i~-th query having the form ~(l_i, r_i)~. Your task is to calculate the complexity of ~P_{l_i \ldots r_i}~, that is the substring obtained by taking the characters of ~P~ from the ~l_i~-th to the ~r_i~-th position, inclusive.

A string ~a~ is a substring of a string ~b~ if ~a~ can be obtained from ~b~ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Input

The first line contains two integers ~n~ and ~q~ (~1 \le n \le 10^5~, ~1 \le q \le 10^5~), denoting the length of ~P~, and the number of queries, respectively.

The next line contains a single bracket sequence ~P~ of length ~n~.

The ~i~-th out of the next ~q~ lines contains two integers ~l_i~ and ~r_i~ (~1 \le l_i \le r_i \le n~), denoting the ~i~-th query.

Output

Output ~q~ lines, the ~i~-th line containing the complexity of ~P_{l_i \ldots r_i}~.

Scoring

  • Subtask 1 (~40~ points): ~n, q \le 1000~.

  • Subtask 2 (~60~ points): No additional constraints.

The total score for this problem is ~100~.

Sample Input 1

8 3
(()))(()
1 8
1 5
2 8

Sample Output 1

2
1
2

Notes

In the first query, the string that we need to answer is ~P_{1\ldots 8}~ or "(()))(()". We can perform the following sequence of operations (the strikethrough characters are those that we delete):

(()))(() ~\rightarrow~ (()))( ~\rightarrow~ )(

This is one of the optimal ways, thus the answer is ~2~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.