假设我们有一个由非负整数组成的数组 $a$。我们可以对该数组执行两种类型的操作：

1. $a_i \leftarrow a_i - 2, a_{i+1} \leftarrow a_{i+1} + 2$。
2. 如果 $a_{i+1} = 0$：$a_i \leftarrow a_i - 1, a_{i+2} \leftarrow a_{i+2} + 1$。

在任何操作之后，所有元素必须保持为非负整数。

显而易见，我们无法无限期地执行这些操作。如果执行完一系列操作后，无法再进行任何有效的操作，我们称这一系列操作为极大操作链。

现在给定一个长度为 $n$ 的数组 $b$。你需要处理两种类型的查询：

• $1 \ p \ x$ — 将 $b_p$ 赋值为 $x$。
• $2 \ l \ r$ — 将子段 $b[l..r]$ 视为数组 $a$。你需要求出在执行某种极大操作链后，该数组中可能包含的零的最大数量。注意，此查询不会真正改变数组 $b$。

输入格式

第一行包含一个整数 $n$，表示数组 $b$ 的长度 ($1 \le n \le 2 \cdot 10^5$)。

第二行包含 $n$ 个空格分隔的整数，表示数组 $b$ 的初始元素 ($0 \le b_i \le 10^5$)。

第三行包含一个整数 $q$，表示查询次数 ($1 \le q \le 2 \cdot 10^5$)。

接下来的 $q$ 行，每行包含一个查询。

对于第一类查询，$1 \le p \le n$ 且 $0 \le x \le 10^5$。

对于第二类查询，$1 \le l \le r \le n$。

输出格式

对于每个第二类查询，在单独的一行中打印答案。答案应按查询的顺序打印。

样例

样例输入 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