parentheses (IATI junior)
Time limit: 0.3 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: data structures, segment tree, prefix sum

IATI Day 2, Junior group
English

![](_page_0_Picture_1.jpeg)

# XV INTERNATIONAL ADVANCED TOURNAMENT IN INFORMATICS
## Task 4. PARENTHESES

⏳ 0.3 sec. 256 MB

*Who doesn't love parentheses?*

Sashka stumbled upon a bracket sequence $S = s_1 s_2 ... s_{2N}$ of $2N$ parentheses, from which $N$ are opening parentheses and $N$ are closing parentheses. She defines the bracket sequence's clumsiness as the minimum number of required swaps of elements to turn it into a regular parentheses sequence. The regular parentheses sequences follow these rules:

*   The empty sequence is a regular parentheses sequence.
*   $S$ is a regular non-empty parentheses sequence if and only if two regular sequences $A$ and $B$ exist such that $S = ( + A + ) + B$, where + denotes the operation concatenation of two sequences.

Sashka wants to know the clumsiness for $Q$ such sequences $T_1, T_2, ..., T_Q$, where the $i$-th of them $T_i = s_{L_i} s_{L_i+1} ... s_{R_i}$ consists of all the elements in $S$ from position $L_i$ to $R_i$ inclusive. **It is guaranteed that every sequence $T_i$ consists of an equal number of opening and closing parentheses.** Write a program **parentheses**, which answers the $Q$ questions.

### Input

The first line of the standard input contains the three integers $N$, $Q$ and $G$, which describe the number of opening parentheses in the sequence, the number of questions and the number of the subtask that the test is from. The second line contains $2N$ parentheses, $s_1 s_2 ... s_{2N}$ respectively. The last $Q$ lines of the standard input contain the integers $L_i$ and $R_i$, which describe the positions for the $i$-th question.

### Output

On the standard output print one number on each line, the $i$-th number being the minimum number of required swaps to turn $T_i$ into a regular parentheses sequence.

### Constraints

*   $1 \le N, Q \le 2 \times 10^5$
*   $1 \le L_i < R_i \le 2 \times N$
*   All questions are different from one another.

### Subtasks

| Subtask | Points | Required subtasks | $N$                  | $Q$                  | Other constraints           |
|---------|--------|-------------------|----------------------|----------------------|-----------------------------|
| 1       | 0      | -                 | -                    | -                    | The examples.               |
| 2       | 5      | -                 | $\leq 4$             | = 1                  | $L_1 = 1, R_1 = 2 \times N$ |
| 3       | 10     | 2                 | $\leq 100$           | = 1                  | $L_1 = 1, R_1 = 2 \times N$ |
| 4       | 10     | 2 - 3             | $\leq 1000$          | = 1                  | $L_1 = 1, R_1 = 2 \times N$ |
| 5       | 15     | 2 - 4             | $\leq 2 \times 10^5$ | = 1                  | $L_1 = 1, R_1 = 2 \times N$ |
| 6       | 15     | -                 | $\leq 2 \times 10^5$ | $\leq 2 \times 10^5$ | Special scoring.*           |
| 7       | 45     | 1 - 6             | $\leq 2 \times 10^5$ | $\leq 2 \times 10^5$ | -                           |

*The points for a subtask are given only if all tests for it and the required subtasks are passed successfully.*

\* Only in the sixth subtask, one test is considered to be successfully passed by your solution, if you have found correctly all answers that are 0. For the other questions in the test (for which the correct answers is not 0), it is only needed that the printed number is an integer in the interval $[1, 10^{18}]$.

### Examples

| Input                  | Output | Explanation of the example |
|------------------------|--------|----------------------------|
| 3 1 1<br>)())((<br>1 6 | 1      | )())(( → (())()            |
| 5 10 1<br>)))(()(()    | 2<br>0 |                            |
| 2 9                    | 1      |                            |
| 6 7                    | 1      |                            |
| 1 10                   | 1      |                            |
| 3 8                    | 1      |                            |
| 7 10                   | 0      |                            |
| 3 10                   | 1      |                            |
| 9 10                   | 1      |                            |
| 4 7                    | 1      |                            |
| 4 5                    | 0        |                            |
| 3 6                    | 0        |                            |

Starter code:

Grader code:

Setup script:

Evaluation script: