You are given a sequence $A_1, A_2, \ldots, A_N$ of length $N$ consisting only of $0$ and $1$. You need to write a program to handle the following two types of queries:

• 1 L R: Flip the numbers in the interval $[L, R]$ of $A$ in order. That is, let the resulting sequence be $B$; then $B_L = A_R$, $B_{L+1} = A_{R-1}$, $\ldots$, $B_R = A_L$, and for all $i$ not in $L \le i \le R$, $B_i = A_i$.
• 2 L R: Output the length of the longest contiguous subsegment consisting entirely of $1$ in the contiguous subarray $A_L, A_{L+1}, \ldots, A_R$. If there is no contiguous subsegment consisting entirely of $1$, output $0$.

Input

The first line contains an integer $N$, the length of the sequence. ($1 \le N \le 100{,}000$)

The second line contains $N$ integers $A_1, A_2, \ldots, A_N$. ($0 \le A_i \le 1$)

The third line contains an integer $M$, the number of queries. ($1 \le M \le 200{,}000$)

The next $M$ lines each contain a query in the format described in the problem statement. ($1 \le L \le R \le N$) It is guaranteed that there is at least one query of type $2$.

Output

For each query of type $2$, output a line containing a single integer representing the answer.

Examples

Input 1

4
0 1 0 1
3
2 2 4
1 3 4
2 2 4

Output 1

1
2