19505번 - Process with Constant Sum 다국어

문제

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.

제한

힌트