Jesteś dany ciąg $A_1, A_2, \ldots, A_N$ długości $N$ składający się wyłącznie z $0$ i $1$. Należy napisać program obsługujący następujące dwa rodzaje zapytań:

• 1 L R: Odwróć kolejność liczb w przedziale $[L, R]$ ciągu $A$. To znaczy, niech otrzymany ciąg to $B$; wtedy $B_L = A_R$, $B_{L+1} = A_{R-1}$, $\ldots$, $B_R = A_L$, a dla wszystkich $i$ nie należących do $L \le i \le R$, $B_i = A_i$.
• 2 L R: Wypisz długość najdłuższego spójnego pododcinka składającego się wyłącznie z jedynek w spójnym podciągu $A_L, A_{L+1}, \ldots, A_R$. Jeśli nie ma spójnego pododcinka składającego się wyłącznie z jedynek, wypisz $0$.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $N$, długość ciągu. ($1 \le N \le 100\,000$)

Drugi wiersz zawiera $N$ liczb całkowitych $A_1, A_2, \ldots, A_N$. ($0 \le A_i \le 1$)

Trzeci wiersz zawiera liczbę całkowitą $M$, liczbę zapytań. ($1 \le M \le 200\,000$)

Kolejne $M$ wierszy zawiera zapytania w formacie opisanym w treści zadania. ($1 \le L \le R \le N$) Gwarantowane jest, że istnieje co najmniej jedno zapytanie typu $2$.

Wyjście

Dla każdego zapytania typu $2$, wypisz wiersz zawierający pojedynczą liczbę całkowitą będącą odpowiedzią.

Przykład

Wejście 1

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

Wyjście 1

1
2