#include<fstream>
using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
#define MAXN 100005
int V[MAXN];
int bsearch0(int st,int dr,int val)
   { 
   int mid;	 			  
   while(st<=dr) 
   {
    mid=(st+dr)/2;
   	if(V[mid]<=val)
	          st=mid+1;
	 else dr=mid-1;
   } 
	mid=(dr+st)/2 ;
	while(V[mid]>val)
	              mid--;
	if(V[mid]==val) return mid;
	 return -1;
}
int bsearch1(int st,int dr,int val) 
   {
   	int mid;
	while(st<=dr){
		mid=(st+dr)/2;
		if(V[mid]<=val)
		     	st=mid+1;
		else dr=mid-1;
    }
    mid=(st+dr)/2;
    while(V[mid]>val)
                 mid--;
    return mid;             
}
int bsearch2(int st,int dr,int val) 
   {
   	int mid;
	while(st<dr){
		mid=(st+dr)/2;
		if(V[mid]<val)
		     	st=mid+1;
		else dr=mid;
    }
    mid=(st+dr)/2;
    while(V[mid]<val)
                 mid++;
    return mid;             
}
int main () {
	int N,M,tip,val,i;
   cin>>N;
	for(i=1;i<=N;i++)
              cin>>V[i];
	         cin>>M;
	 for(i=1;i<=M;i++){
	  cin>>tip>>val;
	     if( tip==0 )  cout<<bsearch0(1,N,val)<<"\n";
	     if( tip==1 )  cout<<bsearch1(1,N,val)<<"\n";
	     if( tip==2 )  cout<<bsearch2(1,N,val)<<"\n";
		} 
	 return 0;
	 }