#include<fstream.h>
int main ()
{
	ifstream fcin("cautbin.in");
	ofstream fcout("cautbin.out");
	int n,i,m,v[100001],a,b,y,x,piv;
	fcin>>n;
	for(i=1;i<=n;i++)
		fcin>>v[i];
	fcin>>m;
	for(i=1;i<=m;i++)
		{fcin>>y>>x;
		piv=n/2+n%2;a=1;b=n;
				  while(v[piv]!=x&&b-a>1)
					  {if(v[piv]<=x)
					        a=piv;
					   else b=piv;
						piv=(a+b)/2;}
						if(y==0&&v[piv]==x)while(v[piv+1]==x)piv++;
						else if(y==1&&v[piv]<=x)while(v[piv+1]<=x)piv++;
							else if(y==2&&v[piv]>=x)while(v[piv-1]>=x)piv--;
								 else if(y==0)piv=-1;
									  else if(y==2&&v[piv]<x)while(v[piv]<x)piv++;
						fcout<<piv<<'\n';
					 }
return 0;
}