//https://infoarena.ro/problema/cautbin
#include <fstream>
using namespace std;
const int MAXN=100001;
int n,m,v[MAXN];
int bin_search(int x,int st,int dr,int opt);
int main()
{
	int opt,val;
	ifstream fin("cautbin.in");
	ofstream fout("cautbin.out");
	
	fin>>n;
	for (int i=0;i<n;i++)
		fin>>v[i];
	fin>>m;
	for (int i=0;i<m;i++)
	{
		fin>>opt>>val;
		fout<<bin_search(val,0,n-1,opt)+1<<'\n';
	}
	fin.close();
	fout.close();
	return 0;
}
int bin_search(int x,int st,int dr,int opt)
{
	int mid=st+(dr-st)/2;
	switch (opt)
	{
	case 0:
		if (dr==st+1 && x!=v[st] && x!=v[dr])
			return -1;
		else
		{
			if (x>v[mid])
				bin_search(x,mid+1,dr,opt);
			else if (x<v[mid])
				bin_search(x,st,mid-1,opt);
			else if (x==v[mid])
			{
				while (v[mid+1]==x)
					mid++;
				return mid;
			}
		}
		break;
	case 1:
		if (dr==st+1 && x!=v[st] && x!=v[dr])
			return st;
		else
		{
			if (x>v[mid])
				bin_search(x,mid+1,dr,opt);
			else if (x<v[mid])
				bin_search(x,st,mid-1,opt);
			else if (x==v[mid])
			{
				while (v[mid+1]==x)
					mid++;
				return mid;
			}
		}
		break;
	case 2:
		if (dr==st+1 && x!=v[st] && x!=v[dr])
			return dr;
		else
		{
			if (x>v[mid])
				bin_search(x,mid+1,dr,opt);
			else if (x<v[mid])
				bin_search(x,st,mid-1,opt);
			else if (x==v[mid])
			{
				while (v[mid-1]==x)
					mid--;
				return mid;
			}
		}
		break;
	}

}