#include <iostream>
#include <fstream>
#include <iostream>
using namespace std;

ifstream ifs("cautbin.in");
ofstream ofs("cautbin.out");

int *a;

int zero(int x,int min,int max);
int  one(int x,int min,int max);
int  two(int x,int min,int max);
int main(){
	int N,M;
	ifs>>N;
	a=new int[N];
	
	for(int i=0;i<N;i++) ifs>>a[i];
	
	ifs>>M;
	
	for(int i=0;i<M;i++){
		int f,x;
		ifs>>f>>x;
		if(f==0)
			ofs<<zero(x,0,N-1)<<endl;
		else if(f==1)
			ofs<<one(x,0,N-1)<<endl;
		else
			ofs<<two(x,0,N-1)<<endl;
	}
	
}

inline int zero(int x,int min,int max){
	int pivot;	
	while(max>=min){
		pivot=(max+min)/2;
		if(x>=a[pivot])
			min=pivot+1;
		else
			max=pivot-1;
	}
	if(a[pivot]==x)
		return pivot+1;
	return -1;
}

inline int one(int x,int min,int max){
	int pivot;	
	while(max>min){
		pivot=(max+min)/2;
		if(x>=a[pivot])
			min=pivot+1;
		else
			max=pivot-1;
	}
	int tmp=a[pivot];
	while(a[pivot]<=tmp)
		pivot++;
	return pivot;
}

inline int two(int x,int min,int max){
	int pivot;	
	while(max>=min){
		pivot=min+(max-min)/2;
		if(x>=a[pivot])
			min=pivot+1;
		else
			max=pivot-1;
	}
	int tmp=a[pivot];
	while(a[pivot]>=tmp)
		pivot--;
	return pivot+1;
}