数列 $A_1, A_2, \ldots, A_N$ が与えられる。この数列は $0$ と $1$ のみからなる長さ $N$ の数列である。以下の 2 種類のクエリを処理するプログラムを作成せよ。

• 1 L R: 数列 $A$ の区間 $[L, R]$ の要素を反転させて並べる。すなわち、結果の数列を $B$ とすると、$B_L = A_R$, $B_{L+1} = A_{R-1}$, $\ldots$, $B_R = A_L$ となり、$L \le i \le R$ 以外のすべての $i$ については $B_i = A_i$ となる。
• 2 L R: 連続する部分配列 $A_L, A_{L+1}, \ldots, A_R$ の中で、すべて $1$ からなる最長の連続部分区間の長さを出力せよ。すべて $1$ からなる連続部分区間が存在しない場合は $0$ を出力せよ。

入力

1 行目には整数 $N$ が与えられる。数列の長さである。($1 \le N \le 100{,}000$)

2 行目には $N$ 個の整数 $A_1, A_2, \ldots, A_N$ が与えられる。($0 \le A_i \le 1$)

3 行目には整数 $M$ が与えられる。クエリの個数である。($1 \le M \le 200{,}000$)

次の $M$ 行のそれぞれには、問題文で説明された形式のクエリが 1 行ずつ与えられる。($1 \le L \le R \le N$) タイプ 2 のクエリが少なくとも 1 つ存在することが保証される。

出力

タイプ 2 のクエリごとに、答えを表す整数を 1 行ずつ出力せよ。

入出力例

入力例 1

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

出力例 1

1
2