Problem Description

Yuan gives you a string $S$ of length $n$. $S$ consists only of ( and ).

She will perform $m$ operations on it. There are two types of operations:

1. 1 l r: She will flip the parentheses from $l$ to $r$, i.e., ( becomes ), and ) becomes (.
2. 2 l r: She wants to know the value of the length of the longest valid parentheses subsequence in the interval $\left[ l,r\right]$, divided by $2$.

Yuan considers the following parentheses sequences to be valid:

1. The empty sequence is a valid sequence.

2. If A is a valid sequence, then (A) is also a valid sequence.

3. If A and B are both valid sequences, then AB is also a valid sequence.

Yuan considers a subsequence of sequence $a$ to be a sequence $[a_{i_1},a_{i_2},...a_{i_k}]$ that satisfies $1\le i_1<i_2<···<i_k \le n$.

Since there are too many operations, she cannot compute them all. Please help her.

Input Format

The first line contains an integer $n$.

The second line contains a string $S$ of length $n$, guaranteed to consist only of ( and ).

The third line contains an integer $m$.

The next $m$ lines each contain three numbers $op$, $l$, $r$, corresponding to the two operations above.

Output Format

For each operation with $op=2$, output one line containing an integer, representing the answer.

6
(()())
5
2 2 3
1 1 3
2 2 3
2 4 6
2 3 6

1
0
1
2

Hint

[Sample Explanation]

• The first extracted string is (), and the answer is $1$.
• After flipping, the string becomes ))(()).
• The second extracted string is )(, and the answer is $0$.
• The third extracted string is ()), and the answer is $1$.
• The fourth extracted string is (()), and the answer is $2$.

[Constraints]

• For $10\%$ of the testdata, $1 \leq n,m \leq 500$.
• For $20\%$ of the testdata, $1 \leq n,m \leq 5000$.
• For $40\%$ of the testdata, $1 \leq n,m \leq 2\times 10^5$.
• Another $10\%$ of the testdata satisfies $op=2$ and is randomly generated.
• Another $15\%$ of the testdata satisfies $op=2$, but the testdata is not guaranteed to be randomly generated.

For all testdata, it is guaranteed that $1\le n \le 5\times 10^5$, $1\le m \le 5 \times 10^5$, $1 \le l \le r \le n$, $op \in \{1,2\}$. The testdata has multiple levels.

Translated by ChatGPT 5