#include <fstream>
using namespace std;
ifstream fin ("cautbin.in");
ofstream fout("cautbin.out");
int n,m,v[100010],st,dr,mid,x,t;
int main () {
	fin>>n;
	for (int i=1;i<=n;i++)
		fin>>v[i];
	fin>>m;
	for (int i=1;i<=m;i++) {
		fin>>t>>x;
		st=1; dr=n;
		while (st<=dr) {
			mid=(dr-st)/2+st;
			if (v[mid]>=x)
				dr=mid-1;
			else
				st=mid+1;
		}
		if (t==0) {
			if (v[st]==x) {
				while (v[st]==x)
					st++;
				fout<<st-1<<"\n";
			}
			else
				fout<<"-1\n";
		}
		if (t==1) {
			while (v[st]<mid)
				st++;
			fout<<st<<"\n";
		}
		if (t==2) {
			while (v[st]>mid)
				st--;
			fout<<st+1<<"\n";
		}
	}
}