#include <iostream>
#include <fstream>

using namespace std;

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

int m,n;
long a[100000];
int ok;
int cauta(int x,int n)
{
	int i,pas;
	for (pas=1;pas<n;pas<<=1);
	for (i=1;pas;pas>>=1)
	{
		if (i+pas<n && a[i+pas]<=x)
			i+=pas;
	}
	
	if (a[i]==x) return i;
		else  {
			     ok=i;
			   return -1;
		}
}


int main()
{
	in>>n;
	long b,v;
	int i;
	for (i=1;i<=n;i++)
		in>>a[i];
	in>>m;
	for (i=1;i<=m;i++)
	{	int x;
		in>>v>>b;
		x=cauta(b,n);
		if (v==0) 
		{
			if (x==-1) out<<-1<<'\n';
			else
			{
				while (a[x]==b) x++;
				x--;
				out<<x<<'\n';
			}
		}
		else
		{
			if (v==1)
			{
				if (x!=-1)
				{
					while (a[x]==b) x++;
						x--;
					out<<x<<'\n';
				}
				else
				{	
						out<<ok<<'\n';
				}
			}
			else
			if (v==2)
			{
				if (x!=-1)
				{
					while (a[x]==b) x--;
					x++;
					out<<x<<'\n';
				}
				else
				{
					out<<ok+1<<'\n';
				}
			}
		}
	}
	return 0;
}