#include<fstream.h>
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n[100001],nr,i,t,x,middle,w; //nr=nr intrebari, t=tip intrebare.
int main(){
	f>>n[0]; //nr termeni in sir;
	for(i=1;i<=n[0];++i)
		f>>n[i];
	f>>nr;
	for(i=1;i<=nr;i++){
		f>>t>>x;
		if(t==0){  //intrebarea 0;
			middle=n[0]/2;
			if(x==n[middle]){
				w=1;
				while(w && middle<n[0]){
					if(n[middle]==n[middle+1]) 
						middle++;
					if(n[middle]!=n[middle+1])
						w=0;
				}
			}
			else if (x<n[middle])
					while(x!=n[middle]) middle--;
				 else
					 while(x!=n[middle])middle++;
		if(middle>n[0]) middle=-1;
		g<<middle<<'\n';
		}
		if(t==1){  //intrebarea 1;
			middle=n[0]/2;
			if(x==n[middle])
				while (x==n[middle]) middle++;
			else if(x<n[middle]){
				while(x!=n[middle])
						middle--;
				middle--;
			}
				else{ while(n[middle]<=x)
						middle ++;
					  middle--;}
		
			
		}
		g<<middle<<'\n';
	}
g.close();
return 0;
}