#include <fstream.h>
long int a[100005],mij;
int caut(long int x, long st, long dr)
{
	while (st<=dr)
	{
		mij=(st+dr)/2;
		if (a[mij]==x)
			return mij;
		else
			if (a[mij]>x)
				dr=mij-1;
			else
				st=mij+1;
	}
	return 0;
}

int main()
{
	long int n,i,j,k,tip,val;
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	f>>n;
	for (i=1;i<=n;i++)
		f>>a[i];
	f>>k;
	for (i=0;i<k;i++)
	{
		f>>tip>>val;
		if (tip==0)
		{
			j=caut(val,1,n);
			if (j)
			{
				while (a[j]==a[j+1])
					j++;
				g<<j<<"\n";
			}
			else
				g<<-1<<"\n";
		}
		else
			if (tip==1)
			{
				j=caut(val,1,n);
				if (j)
				{
					while (a[j]==a[j+1])
						j++;
				}
				else
				{
					while (a[mij]==a[mij-1])
						mij--;
					j=mij-1;
				}
				g<<j<<"\n";
			}
			else
			{
				j=caut(val,1,n);
				if (j)
					while (a[j]==a[j-1])
						j--;
				else
					j=mij;
				g<<j<<"\n";
			}
	}
	/*{f>>val;
	if (caut(val,1,n))
		g<<"este pe "<<caut(val,1,n)<<"\n";
	else
		g<<"nu e"<<"("<<mij<<")"<<"\n";}*/
	f.close();
	g.close();
}