길이가 $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$)

둘째 줄에는 $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$번 쿼리의 결과를 한 줄에 하나씩 출력한다.

Sample

Input

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

Output

1
2