#include <fstream>
#include <iostream>
using namespace std;
int n,a[100001];
inline int f0(int x){
	int st=1,dr=n,rez = -1;
	while(st<=dr){
		int m = st+(dr-st)/2;
//		cout<<m<<" ";
		if( a[m] == x)
			 rez = m;
		if(a[m]<x)
				 st = m+1;
		else
			dr= m-1;
	}
	return rez;
}
inline int f1(int x){
	int st=1,dr=n,rez;
	while(st<=dr){
		int m = st+(dr-st)/2;
		if(a[m]<=x)
			rez = m, st= m+1;
		else
			dr = m-1;
	}
	return rez;
}
inline int f2(int x){
	int st=1,dr=n, rez;
	while(st<=dr){
		int m =st+(dr-st)/2;
		if(a[m]>=x)
			rez = m , dr = m-1;
		else
			st = m+1;

	}
	return rez;
}
int main(){
	ifstream fin("cautbin.in");
	fin>>n;
	for(int i=1;i<=n;i++)
		fin>>a[i];
	int m;
	fin>>m;
	ofstream fout("cautbin.out");
	for( ; m ; --m){
		int c,x;
		fin>>c>>x;
		switch(c){
			case 0:fout<<f0(x)<<endl;break;
			case 1:fout<<f1(x)<<endl;break;
			case 2:fout<<f2(x)<<endl;break;
		}
	}
	fout.close();
	return 0;
}