给定一个长度为 $N$，仅由 $0$ 和 $1$ 组成的序列 $A_1, A_2, \ldots, A_N$。你需要编写程序处理以下两种查询：

• 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$ 的连续子段 $A_L, A_{L+1}, \ldots, A_R$ 中，最长的全为 $1$ 的连续子段长度。如果不存在全为 $1$ 的连续子段，则输出 $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