#include<iostream>
#include<fstream>
using namespace std;
int v[100001];
int cautarebinara(int p, int q, int x)
{
	int mij,poz;
	poz=-1;
	while(p<=q) {
		mij=(p+q)/2;
		if(x<v[mij])
			q=mij-1;
		else if(x>=v[mij]){
			p=mij+1;
			poz=mij;
		}
	}
	return poz;
}
int cautarebinara1(int p, int q, int x)
{
	int mij,poz;
	poz=-1;
	while(p<=q) {
		mij=(p+q)/2;
		if(x<v[mij])
			q=mij-1;
		else if(x>=v[mij]) {
			poz=mij;
			p=mij+1;
		}
	}
	return poz;
}
int cautarebinara2(int p, int q, int x)
{
	int mij,poz;
	poz=-1;
	while(p<=q) {
		mij=(p+q)/2;
		if(x<=v[mij]) {
			poz=mij;
			q=mij-1;
		}
		else if(x>v[mij]) 
			p=mij+1;
	}
	return poz;
}

int main ()
{
	int n,m,i,op,x;
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	f>>m;
	for(i=1;i<=m;i++) {
		f>>op>>x;
		if(op==0)
			g<<cautarebinara(1,n,x)<<'\n';
		else if(op==1)
			g<<cautarebinara1(1,n,x)<<'\n';
		else g<<cautarebinara2(1,n,x)<<'\n';
	}
	f.close();
	g.close();
	return 0;
}