#include<cstdio>
#include<algorithm>
using namespace std;

#define NMAX 100005

FILE *f=fopen("cautbin.in","r");
FILE *g=fopen("cautbin.out","w");


long n,m,v[NMAX],y;

void citire()
{ 
	fscanf(f,"%ld",&n);
	
	for (long i=1;i<=n;i++)
	fscanf(f,"%ld",&v[i]);

	fscanf(f,"%ld",&m);
}

int main()
{
	citire();
	
	for (long i=1;i<=m;i++)
	{
		long t,x;
		fscanf(f,"%ld%ld",&t,&x);
		
	if (t==0)
		{ y=upper_bound(v+1,v+n+1,x)-v-1;
		
		if(v[y]==x)
			fprintf(g,"%ld\n",y);
		else
			fprintf(g,"-1\n");
		}
	if (t==1)
		{ y=upper_bound(v+1,v+n+1,x)-v-1;
	      fprintf(g,"%ld\n",y);
		}
	if (t==2)
		{ y=lower_bound(v+1,v+n+1,x)-v;
	 fprintf(g,"%ld\n",y);
	    }
	}
return 0;}