Ashu and Shanu are best buddies. One day Shanu gives Ashu a problem to test his intelligence.He gives him an array of N natural numbers and asks him to solve the following queries:-

Query 0:- modify the element present at index i to x.
Query 1:- count the number of even numbers in range l to r inclusive.
Query 2:- count the number of odd numbers in range l to r inclusive.    

input:
First line of the input contains the number N. Next line contains N natural numbers. 
Next line contains an integer Q followed by Q queries.
0 x y - modify the number at index x to y.  
1 x y - count the number of even numbers in range l to r inclusive.
2 x y - count the number of odd numbers in range l to r inclusive.  

Constraints:
1 ≤ N,Q ≤ 10^5
1 ≤ l ≤ r ≤ N  
0 ≤ Ai ≤ 10^9
1 ≤ x ≤ N
0 ≤ y ≤ 10^9

Note:- indexing starts from 1.

SAMPLE INPUT
6
1 2 3 4 5 6
4
1 2 5
2 1 4
0 5 4
1 1 6

SAMPLE OUTPUT
2
2
4
import math

n = int(raw_input())
arr = map(int,raw_input().split())
q = int(raw_input())
#tree stores count of odd number
height = int(math.ceil(math.log(n,2)))
tn = int(math.pow(2,height))
tree = [0]*(2*tn)
# print 2*tn

def buildSegTree(node,l,r,arr):
	if l==r:
		tree[node] = arr[l]%2
	else:
		mid = (l+r)/2
		buildSegTree(2*node,l,mid,arr)
		buildSegTree(2*node+1,mid+1,r,arr)
		tree[node] = tree[2*node]+tree[2*node+1]
buildSegTree(1,0,n-1,arr)
# print tree

def countOdd(node,start,end,l,r):
	if r<start or l>end:
		return 0
	if l<=start and r>=end:
		return tree[node]
	mid = (start+end)/2
	return countOdd(2*node,start,mid,l,r)+ countOdd(2*node+1,mid+1,end,l,r)

def countEven(l,r):
	return r-l+1 - countOdd(1,0,n-1,l,r)

def updateUtil(node,l,r,idx,val):
	if l==r:
		tree[node] = val%2 
	else:
		mid = (l+r)/2
		if idx<=mid:
			updateUtil(2*node,l,mid,idx,val)
		else:
			updateUtil(2*node+1,mid+1,r,idx,val)
		tree[node] = tree[2*node+1]+tree[2*node]
	

def update(x,y):
	# inc = y-arr[x]
	# arr[x]=y
	# print x,inc,arr
	updateUtil(1,0,n-1,x,y)
	
# print countOdd(1,0,n-1,1,4)

while q>0:
	typ,x,y = map(int,raw_input().split())
	if typ == 1:
		print countEven(x-1,y-1)
	if typ == 2:
		print countOdd(1,0,n-1,x-1,y-1)
	if typ == 0:
		update(x-1,y)
	q-=1