Вам дана последовательность $A_1, A_2, \ldots, A_N$ длины $N$, состоящая только из $0$ и $1$. Необходимо написать программу для обработки запросов двух типов:

• 1 L R: Обратить порядок чисел на отрезке $[L, R]$ последовательности $A$. То есть, пусть результирующая последовательность будет $B$; тогда $B_L = A_R$, $B_{L+1} = A_{R-1}$, $\ldots$, $B_R = A_L$, а для всех $i$, не лежащих в $L \le i \le R$, $B_i = A_i$.
• 2 L R: Вывести длину самого длинного непрерывного подотрезка, состоящего целиком из $1$, в подмассиве $A_L, A_{L+1}, \ldots, A_R$. Если непрерывного подотрезка из одних единиц нет, вывести $0$.

Входные данные

Первая строка содержит целое число $N$ — длину последовательности. ($1 \le N \le 100\,000$)

Вторая строка содержит $N$ целых чисел $A_1, A_2, \ldots, A_N$. ($0 \le A_i \le 1$)

Третья строка содержит целое число $M$ — количество запросов. ($1 \le M \le 200\,000$)

Следующие $M$ строк содержат по одному запросу в формате, описанном в условии задачи. ($1 \le L \le R \le N$) Гарантируется, что есть хотя бы один запрос типа $2$.

Выходные данные

Для каждого запроса типа $2$ выведите строку, содержащую одно целое число — ответ.

Примеры

Входные данные 1

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

Выходные данные 1

1
2