Vous disposez d'une séquence $A_1, A_2, \ldots, A_N$ de longueur $N$ constituée uniquement de $0$ et de $1$. Vous devez écrire un programme pour traiter les deux types de requêtes suivants :

• 1 L R : Inverser l'ordre des nombres dans l'intervalle $[L, R]$ de $A$. C'est-à-dire, soit $B$ la séquence résultante ; alors $B_L = A_R$, $B_{L+1} = A_{R-1}$, $\ldots$, $B_R = A_L$, et pour tout $i$ n'appartenant pas à $L \le i \le R$, $B_i = A_i$.
• 2 L R : Afficher la longueur du plus long sous-segment contigu ne contenant que des $1$ dans le sous-tableau contigu $A_L, A_{L+1}, \ldots, A_R$. S'il n'y a aucun sous-segment contigu ne contenant que des $1$, afficher $0$.

Entrée

La première ligne contient un entier $N$, la longueur de la séquence. ($1 \le N \le 100\,000$)

La deuxième ligne contient $N$ entiers $A_1, A_2, \ldots, A_N$. ($0 \le A_i \le 1$)

La troisième ligne contient un entier $M$, le nombre de requêtes. ($1 \le M \le 200\,000$)

Les $M$ lignes suivantes contiennent chacune une requête au format décrit dans l'énoncé. ($1 \le L \le R \le N$) Il est garanti qu'il y a au moins une requête de type $2$.

Sortie

Pour chaque requête de type $2$, afficher une ligne contenant un entier représentant la réponse.

Exemples

Entrée 1

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

Sortie 1

1
2