합이 일정한 과정

원소가 모두 음이 아닌 정수인 배열 $a$가 있다고 하자. 이 배열에 다음 두 종류의 연산을 적용할 수 있다.

1. $a_i \gets a_i - 2$, $a_{i+1} \gets a_{i+1} + 2$.
2. $a_{i+1} = 0$이면 $a_i \gets a_i - 1$, $a_{i+2} \gets a_{i+2} + 1$.

연산을 적용한 뒤에도 모든 원소는 0 이상이어야 한다.

연산을 무한히 반복할 수는 없다. 더 이상 유효한 연산이 없는 연산의 연속을 극대라고 부른다.

길이 $n$인 배열 $b$가 주어진다. 다음 두 종류의 쿼리를 처리하라.

• "1 $p$ $x$": $b_p \gets x$로 대입한다.
• "2 $l$ $r$": 부분 배열 $b[l..r]$을 배열 $a$로 본다. 극대 연산의 연속을 적용한 뒤 이 배열에 있을 수 있는 0의 최대 개수를 구하라. 이 쿼리에서 배열 $b$는 실제로 바뀌지 않는다.

첫째 줄에 배열 $b$의 길이 $n$ ($1 \le n \le 2 \cdot 10^{5}$)이 주어진다.

둘째 줄에는 배열 $b$의 초기 원소 $n$개가 공백으로 구분되어 주어진다 ($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$이다.

두 번째 유형의 각 쿼리에 대해 답을 한 줄에 하나씩, 입력된 순서대로 출력한다.