using namespace std;
#include<iostream>
#include<fstream>
const int N=100003;
int v[N];
int caut0(int s, int d, int x)
{
	if(s==d)
		if(x!=v[s])
			return -1;
		else
			return s;
	int m=(s+d+1)/2;
	if(x<v[m])
		return caut0(s,m-1,x);
	else
		return caut0(m,d,x);
}

int caut1(int s, int d, int x)
{
	if(s==d)
		if(v[s]<=x)
			return s;
		else
			return s-1;
	int m=(s+d)/2;
	if(x<=v[m])
		return caut1(s,m,x);
	else
		return caut1(m+1,d,x);
}
int caut2(int s, int d, int x)
{
	if(s==d)
		if(x<=v[s])
			return s;
		else 
			return s+1;
	int m=(s+d)/2;
	if(x<=v[m])
		return caut2(s,m,x);
	else	
		return caut2(m+1,d,x);
}

int main()
{
	ifstream in("cautbin.in");
	ofstream out("cautbin.out");
	int tip,val,n,m,i;
	in>>n;
	for(i=1;i<=n;++i)
		in>>v[i];
	in>>m;
	while(m--){
		in>>tip>>val;
		if(tip==0)
			out<<caut0(1,n,val);
		if(tip==1)
			out<<caut1(1,n,val);
		if(tip==2)
			out<<caut2(1,n,val);
		out<<"\n";
	}
	in.close();
	out.close();
	return 0;
}