#include<fstream>
using namespace std;
long mij,st,dr,i,x,m,n,poz,a[100010],op;
int main(){
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	f>>n;
	for (i=1;i<=n;i++)
		f>>a[i];
	f>>m;
	for (i=1;i<=m;i++){
		f>>op>>x;
		if (op==0){
			poz=0;
			st=1;dr=n;
			while(st<=dr) {
				mij=(dr+st)/2;
				if (a[mij]==x & poz<mij)  {
					poz=mij;
					st=mij+1;
				}
				else
					if (a[mij]==x) st=mij+1;
					else
						if (a[mij]<x) st=mij+1;
							else dr=mij-1;
			}
			if (poz==0) g<<"-1"<<"\n";
			else g<<poz<<"\n";
		}
		if (op==1) {
			poz=0;
			st=1;dr=n;
			while(st<=dr) {
				mij=(dr+st)/2;
				if (a[mij]<=x & poz<mij)  {
					poz=mij;
					st=mij+1;
				}
				else
					if (a[mij]<=x) st=mij+1;
					else
						if (a[mij]>x) dr=mij-1;
			}
			if (poz==0) g<<"-1"<<"\n";
			else g<<poz<<"\n";
		}
		if (op==2){
			poz=n+1;
			st=1;dr=n;
			while(st<=dr) {
				mij=(dr+st)/2;
				if (a[mij]>=x & poz>mij)  {
					poz=mij;
					dr=mij-1;
				}
				else
					if (a[mij]>=x) dr=mij-1;
					else
						if (a[mij]<x) st=mij+1;
					
			}
			if (poz==n+1) g<<"-1"<<"\n";
			else g<<poz<<"\n";
		}
	}
	return 0;
}