#include<stdio.h>
FILE *fin=fopen("cautbin.in","r");
FILE *fout=fopen("cautbin.out","w");
int n,m,t,tt,i,v[100010],tip,x,poz,p,u;

int main(){
	
	fscanf(fin,"%d",&n);
	
	for(i=1;i<=n;i++){
		fscanf(fin,"%d",&v[i]);
	}
	
	fscanf(fin,"%d",&t);
	
	for(tt=1;tt<=t;tt++){
		fscanf(fin,"%d %d",&tip, &x);
		
		if(tip==0){
			poz=-1;
			
			p=1;
			u=n;
			
			while(p<=u){
				m=p+(u-p)/2;
				
				if(v[m]==x){
					if(m>poz) poz=m;
					p=m+1;
				}
				else
				if(v[m]<x){
					p=m+1;
				}
				else{
					u=m-1;
				}
			}
			
		}
		else
		if(tip==1){
			poz=-1;
			
			p=1;
			u=n;
			
			while(p<=u){
				m=p+(u-p)/2;
				
				if(v[m]<=x){
					if(m>poz) poz=m;
					p=m+1;
				}
				else{
					u=m-1;
				}
			}
		}
		else
		if(tip==2){
			poz=n+1;
			
			p=1;
			u=n;
			
			while(p<=u){
				m=p+(u-p)/2;
				
				if(v[m]>=x){
					if(m<poz) poz=m;
					u=m-1;
				}
				else{
					p=m+1;
				}
			}
		}
		
		fprintf(fout,"%d\n",poz);
		
	}
	
	
	return 0;
}