#include <bits/stdc++.h>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100001];
int main()
{
	int n,m,f,x,mijl;
	fin>>n;
	for(int i=1; i<=n; i++) {
		fin>>v[i];
	}
	fin>>m;
	for(int ds=1; ds<=m; ds++) {
		fin>>f>>x;
		if(f==0) {
			int st=1,dr=n,poz=-1;
			while(st<=dr) {
				mijl=(st+dr)/2;
				if(v[mijl]<=x) {
					if(v[mijl]==x) {
						poz=mijl;
					}
					st=mijl+1;
				} else {
					dr=mijl-1;
				}
			}
			fout<<poz<<'\n';
		}
		if(f==1) {
			int st=1,dr=n,poz=-1;
			while(st<=dr) {
				mijl=(st+dr)/2;
				if(v[mijl]<=x) {
					poz=mijl;
					st=mijl+1;
				} else {
					dr=mijl-1;
				}
			}
			fout<<poz<<'\n';
		}
		if(f==2) {
			int st=1,dr=n,poz=-1;
			while(st<=dr) {
				mijl=(st+dr)/2;
				if(v[mijl]>=x) {
					poz=mijl;
					dr=mijl-1;
				} else {
					st=mijl+1;
				}
			}
			fout<<poz<<'\n';
		}
	}
	return 0;
}