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

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

int a[100001];
int N,M;
int zero(int x);
int  one(int x);
int  two(int x);
int main(){
	
	ifs>>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)<<"\n";
		else if(f==1)
			ofs<<one(x)<<"\n";
		else
			ofs<<two(x)<<"\n";
	}

}

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

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

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