def cautBin(qType, x, arr):
	n = len(arr)
	left = 0
	right = n - 1
	lastPos = -1
	while left <= right:
		mid = (left + right) // 2
		if arr[mid] == x:
			lastPos = mid
			if qType < 2:
				left = mid + 1
			else:
				right = mid - 1
		elif arr[mid] > x:
			if qType == 2:
				lastPos = mid
			right = mid - 1
		else:
			if qType == 1:
				lastPos = mid
			left = mid + 1
	return lastPos + 1


def main():
	f = open("cautbin.in", "r")
	w = open("cautbin.out", "w")
	n = int(f.readline())
	arr = [int(x) for x in f.readline().split()]
	m = int(f.readline())
	for _ in range(m):
		qType, val = f.readline().split(' ')
		qType = int(qType)
		val = int(val)
		pos = cautBin(qType, val, arr)
		w.write(str(pos) + "\n")
main()