#include<fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100001];
int binsearch0(int low , int high , int x){
	 int mid ;
	 while(low<high){
		 mid=(low+high)/2;
		 if(x<=v[mid])
			 low=mid+1;
		 else
			 high=mid-1;
	 }
	 mid=(low+high)/2;
	 if(v[mid] > x) mid--;
	 if(v[mid]==x)
		 return mid;
return -1;
}
int binsearch1(int low , int high , int x){
	 int mid ;
	 while(low<high){
		 mid=(low+high)/2;
		 if(x<=v[mid])
			 low=mid+1;
		 else
			 high=mid;
	 }
	 mid=(low+high)/2;
	 if(v[mid] > x ) mid--;
	 if(v[mid]==x)
		 return mid;
return -1;
}
int binsearch2(int low , int high , int x){
	 int mid ;
	 while(high>low){
		 mid=(high-low)/2;
		 if(x<=v[mid])
			 low=mid+1;
		 else
			 high=mid;
	 }
	 mid=(low+high)/2;
	 if(v[mid] < x) mid++;
	 if(v[mid]==x)
		 return mid;
return -1;
}
int main(){
	 int n , m , i , val , tip ;
	 fin>>n;
	 for(i=1 ; i<=n ; i++)
		 fin>>v[i];
	 fin>>m;
	 while(m--){
		 fin>>tip>>val;
		 if(tip==0)
			 fout<<binsearch0(1,n,val)<<"\n";
		 else if(tip==1)
			 fout<<binsearch1(1,n,val)<<"\n";
		 else
			 fout<<binsearch2(1,n,val)<<"\n";
	 }
return 0;
}