#include <bits/stdc++.h>
using namespace std;
int n, a[100001],i, t, u, v; 
int binary_search(int u, int v){
	 int st=1, dr=n, mij;
	while (st<=dr) {
		mij=st+(dr-st)/2;
		if ((u==0) || (u==1)) 
	    {	if (v>=a[mij])st=mij+1; else dr=mij-1; }
		else if (v<=a[mij]) dr=mij-1; else st=mij+1;
	}
	if (u==0) {
		if (a[st-1]==v) return st-1; else return -1;}
	if (u==1) return dr; else return dr+1;
	}
int main() {
	ifstream cin("cautbin.in");
	ofstream cout("cautbin.out");
	cin >> n;
	for (i=1; i<=n; i++)
	cin >> a[i];
	cin >> t;
	for (i=1; i<=t; i++){
			cin >> u >> v; 
			cout << binary_search(u,v);
			}
	return 0;
}