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