Se te da una secuencia $A_1, A_2, \ldots, A_N$ de longitud $N$ que consiste solo de $0$ y $1$. Necesitas escribir un programa para manejar los siguientes dos tipos de consultas:

• 1 L R: Invierte los números en el intervalo $[L, R]$ de $A$ en orden. Es decir, sea la secuencia resultante $B$; entonces $B_L = A_R$, $B_{L+1} = A_{R-1}$, $\ldots$, $B_R = A_L$, y para todo $i$ que no esté en $L \le i \le R$, $B_i = A_i$.
• 2 L R: Imprime la longitud del subsegmento continuo más largo que consiste enteramente de $1$ en el subarreglo continuo $A_L, A_{L+1}, \ldots, A_R$. Si no hay ningún subsegmento continuo que consista enteramente de $1$, imprime $0$.

Entrada

La primera línea contiene un entero $N$, la longitud de la secuencia. ($1 \le N \le 100{,}000$)

La segunda línea contiene $N$ enteros $A_1, A_2, \ldots, A_N$. ($0 \le A_i \le 1$)

La tercera línea contiene un entero $M$, el número de consultas. ($1 \le M \le 200{,}000$)

Las siguientes $M$ líneas contienen cada una una consulta en el formato descrito en el enunciado. ($1 \le L \le R \le N$) Se garantiza que hay al menos una consulta de tipo $2$.

Salida

Para cada consulta de tipo $2$, imprime una línea que contenga un único entero representando la respuesta.

Ejemplos

Entrada 1

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

Salida 1

1
2