Bạn được cho một dãy $A_1, A_2, \ldots, A_N$ độ dài $N$ chỉ gồm $0$ và $1$. Bạn cần viết chương trình xử lý hai loại truy vấn sau:

• 1 L R: Đảo ngược thứ tự các số trong đoạn $[L, R]$ của $A$. Cụ thể, gọi dãy kết quả là $B$; khi đó $B_L = A_R$, $B_{L+1} = A_{R-1}$, $\ldots$, $B_R = A_L$, và với mọi $i$ không nằm trong $L \le i \le R$, $B_i = A_i$.
• 2 L R: Đưa ra độ dài của đoạn con liên tiếp dài nhất chỉ gồm toàn số $1$ trong đoạn con $A_L, A_{L+1}, \ldots, A_R$. Nếu không có đoạn con liên tiếp nào chỉ gồm toàn số $1$, đưa ra $0$.

Dữ liệu vào

Dòng đầu chứa một số nguyên $N$, độ dài của dãy. ($1 \le N \le 100{,}000$)

Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \ldots, A_N$. ($0 \le A_i \le 1$)

Dòng thứ ba chứa một số nguyên $M$, số lượng truy vấn. ($1 \le M \le 200{,}000$)

$M$ dòng tiếp theo, mỗi dòng chứa một truy vấn theo định dạng được mô tả trong đề bài. ($1 \le L \le R \le N$) Dữ liệu đảm bảo có ít nhất một truy vấn loại $2$.

Dữ liệu ra

Với mỗi truy vấn loại $2$, in ra một dòng chứa một số nguyên là kết quả.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1
2