# include <stdio.h>

# define in_file "cautbin.in"
# define out_file "cautbin.out"
# define NMAX 100001

int v[NMAX];

int N,M,i,j,k,res;

inline int solve0(int val){
	int low=0,high=N-1,pos;
	while(low<=high){
		pos=(low+high)/2;
		if(v[pos]==val){	
			while(v[pos+1]==v[pos])
				pos++;
			return pos+1;/*vectorul are indici de la 1 la N*/
		}
		else if(v[pos]<val)
			low=pos+1;
		else
			high=pos-1;
	}
	return -1;
}

inline int solve1(int val){
	int low=0,high=N-1,pos;
	while(low<=high){
		pos=(low+high)/2;
		if(v[pos]==val){	
			while(v[pos-1]==v[pos])
				pos--;
			return pos;
		}
		else if(v[pos]<val)
			low=pos+1;
		else
			high=pos-1;
	}
	if(v[pos]<=val)
		return pos+1;
	return pos;
}

inline int solve2(int val){
	int low=0,high=N-1,pos;
	while(low<=high){
		pos=(low+high)/2;
		if(v[pos]==val){	
			while(v[pos-1]==v[pos])
				pos--;
			return pos;
		}
		else if(v[pos]<val)
			low=pos+1;
		else
			high=pos-1;
	}
	if(v[pos]<=val)
		return pos;
	return pos+1;
}

int solve(int type,int val){
	if(type==0)
		return solve0(val);
	else if(type==1)
		return solve1(val);
	else
		return solve2(val);
}

int main (){
	FILE *f=fopen(in_file,"rt");
	FILE *g=fopen(out_file,"wt");
	
	fscanf(f,"%d",&N);
	for (i=0;i<N;i++)
		fscanf(f,"%d",&v[i]);
	
	fscanf(f,"%d",&M);

	for (i=0;i<M;i++){
		fscanf(f,"%d %d",&j,&k);
		res=solve(j,k);
		fprintf(g,"%d\n",res);
	}
		
	fclose(f);
	fclose(g);
	
	return 0;
}