32493번 - PARENTHESES 서브태스크스페셜 저지다국어

문제

Who doesn't love parentheses?

Sashka stumbled upon a bracket sequence $S=s_1 s_2 \dots s_{2N}$ of 2ドルN$ 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 iff 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, \dots,T_Q,ドル where the $i$-th of them $T_i=s_{L_i} s_{L_i+1} \dots 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 equal number of opening and closing parentheses. Write a program parentheses, which answers the $Q$ questions.

입력

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 2ドルN$ parentheses, $s_1 s_2 \dots 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.

출력

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.

제한

• 1ドル \leq N, Q \leq 2 \times 10^5$
• 1ドル \leq L_i < R_i \leq 2 \times N$
• All questions are different from one another.

서브태스크

^* 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 a integer in the interval $[1, 10^{18}]$.

힌트