#include<fstream>
#define lmax 110000
using namespace std;
int n,v[lmax],op,x;
int caut(int st,int dr){
	if(st>dr)return st;
	long long m=(st+dr)/2;
	if(x>=v[m])return caut(m+1,dr);
	else return caut(st,m-1);
}
int caut2(int st,int dr){
	if(st>=dr)return st;
	long long m=(st+dr)/2;
	if(x>=v[m])return caut(m+1,dr);
	else return caut(st,m-1);
}
int cautf(int st, int dr){
	if(st>dr)return st;
	long m=(st+dr)/2;
	if(x>v[m])return caut(m+1,dr);
	else return caut(st,m-1);
}
int main(){
	int i,et,b;
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	f>>et;
	while(et!=0){et--;
		f>>op>>x;
		if(op==1)b=caut(1,n);
		if(op==2)b=caut2(1,n);
		if(op==2)b=cautf(1,n);
		else b=cautf(1,n);
		if(op==0){
			 if(v[b-1]!=x)g<<-1;
			 else g<<b-1;
		}
		if(op==1)g<<b-1;
		if(op==2){
			if(v[b-1]!=x)
				{if(b==n+1)g<<b-1;
					else g<<b;}
				 else g<<b-1;}
		g<<'\n';}
	f.close();
	g.close();
}