#include<iostream>
#include<fstream>
using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");

int n, m, v[100000], x;	

int cauta0(int a, int b)
{
	if(a==b)
	{
		if(x==v[a])
			return a+1;
		return -1;
	}
	int m=(a+b+1)/2;
	if(x<v[m])
		return cauta0(a, m-1);
	return cauta0(m, b);
}

int cauta1(int a, int b)
{
	if(a==b)
		return a+1;
	int m=(a+b+1)/2;
	if(x<v[m])
		return cauta1(a, m-1);
	return cauta1(m, b);
}

int cauta2(int a, int b)
{
	if(a==b)
		return a+1;
	int m=(a+b)/2;
	if(x<=v[m])
		return cauta2(a, m);
	return cauta2(m+1, b);
}

int main()
{
	int i, k;
	in>>n;
	for(i=0; i<n; i++)
		in>>v[i];
	in>>m;
	for(i=0; i<m; i++)
	{
		in>>k>>x;
		if(k==0)
			out<<cauta0(1, n)<<"\n";
		if(k==1)
			out<<cauta1(1, n)<<"\n";
		if(k==2)
			out<<cauta2(1, n)<<"\n";
	}
	return 0;
}