#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=(st+dr)/2;
	if (V[mid]==val) { while(V[mid]==val)
	                                mid++;
						mid--;
						return mid;
						}				 
    if(st==dr)
	          return -1;
	if(val<=V[mid])  return bsearch0(st,mid,val);
	  else return bsearch0(mid+1,dr,val);
}
int bsearch1(int st,int dr,int val) {
	int mid=(st+dr)/2;
	if (V[mid]==val) { while(V[mid]==val)
	                                mid++;
						mid--;
						return mid;
						}				 
    if(st==dr) { while(V[dr]>=val) 
	                   dr--;
				dr++;
				return dr;
				}	    
	          
	if(val<=V[mid])  return bsearch0(st,mid,val);
	  else return bsearch0(mid+1,dr,val);
}  
int bsearch2(int st,int dr,int val) {
	int mid=(st+dr)/2;
	if (V[mid]==val) { while(V[mid]==val)
	                                mid--;
						mid++;
						return mid;
						}				 
    if(st==dr) { while(V[dr]<val) 
	                   dr++;
				dr--;
				return dr;
				}	    
	          
	if(val<=V[mid])  return bsearch0(st,mid,val);
	  else return bsearch0(mid+1,dr,val);
}  		
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";
		} 
		system("PAUSE");  
	 return 0;
	 }