#include <fstream>
using namespace std;

int nr[100001];
int cautbin0(int x,int lo,int hi);
int cautbin1(int x,int lo,int hi);
int cautbin2(int x,int lo,int hi);
int main(int argc, char *argv[]){
	ifstream in;
	ofstream out;
	int n,m,x;
	short int tip;
	
	in.open("cautbin.in");
	in>>n;
	for(int i = 1;i <= n;++i){
		in >> nr[i];
	}
	in >> m;
	
	out.open("cautbin.out");
	for(int i = 0;i < m;++i){
		
		in >> tip >> x;
		
		if(tip == 0)
			out<<cautbin0(x, 1, n);
		if(tip == 1)
			out<<cautbin1(x, 1, n);
		if(tip == 2)
			out<<cautbin2(x, 1, n);
		
		out<<endl;
	}
	out.close();
	in.close();
	return 0;
}

int cautbin0(int x,int lo,int hi){
	int mid;
	
	while(lo <= hi){
		mid = lo + (hi - lo)/2;
		if(nr[mid] <= x)
			lo = mid + 1;
		else 
			hi = mid - 1;
	}
	
	if(x < nr[mid]) mid--;
	if(x == nr[mid])
		return mid;
	return -1;
}

int cautbin1(int x,int lo,int hi){
	int mid;
	
	while(lo < hi){
		mid = lo + (hi - lo)/2;
		if(nr[mid] <= x)
			lo = mid + 1;
		else 
			hi = mid;
	}
	mid = (lo+hi)/2;
	
	if(nr[mid] > x)
		mid--;
	return mid;
}

int cautbin2(int x,int lo,int hi){
	int mid;
	
	while(lo < hi){
		mid = lo + (hi - lo)/2;
		if(nr[mid] < x)
			lo = mid + 1;
		else 
			hi = mid;
	}
	
	mid = (lo+hi)/2;
	return mid;
}