시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

Suppose we have an array $a$ whose elements are non-negative integers. We can apply operations of two types to this array:

  1. $a_{i} \gets a_{i} - 2$, $a_{i+1} \gets a_{i+1} + 2$.
  2. If $a_{i+1} = 0$: $a_{i} \gets a_{i} - 1$, $a_{i+2} \gets a_{i+2} + 1$.

After any operation, all the elements must remain non-negative.

It is easy to see that we cannot do such operations indefinitely. We'll call a chain of operations maximal if no valid operation can occur after performing this chain of operations.

Now you are given an array $b$ of length $n$. Your should handle two types of queries:

  • "1 $p$ $x$" --- assignment $b_{p} \gets x$.
  • "2 $l$ $r$" --- let us treat the subsegment $b[l..r]$ as array $a$. You have to find the maximum number of zeroes which can be in that array after applying some maximal chain of operations. Note that we don't really change the array $b$ during this query.

입력

The first line of input contains one integer $n$, the length of array $b$ ($1 \le n \le 2 \cdot 10^{5}$).

The second line contains $n$ integers separated by spaces: the initial elements of array $b$ ($0 \le b_{i} \le 10^{5}$).

The third line contains one integer $q$, the number of queries ($1 \le q \le 2 \cdot 10^{5}$).

Each of the next $q$ lines contains a query.

For queries of the first type, $1 \le p \le n$ and $0 \le x \le 10^{5}$.

For queries of the second type, $1 \le l \le r \le n$.

출력

For each query of the second type, print the answer on a separate line. Answers should be printed in the same order as queries.

예제 입력 1

3
2 2 2
9
2 1 3
1 1 1
2 1 3
1 2 1
2 1 3
1 1 4
2 1 3
2 1 2
2 2 3

예제 출력 1

2
2
0
1
1
0

예제 입력 2

1
20500
1
2 1 1

예제 출력 2

0