#include<stdio.h>
#define nmax 100001
FILE *f=fopen("cautbin.in","r"), *g=fopen("cautbin.out","w");
int n,m,i,k,N,NN,p,x,a[nmax];
int main()
{
	fscanf(f,"%d",&n,&m);
	for(i=1;i<=n;i++)
		fscanf(f,"%d",&a[i]);
	
	for(N=1;N<=n; N<<=1);
	
	fscanf(f,"%d",&m);
	for(i=1;i<=m;i++)
	{
		fscanf(f,"%d %d",&p,&x);
		if(p==0)
		{
			k=0;
			for(NN=N;NN;NN>>=1)
			{
				if(k+NN<=n && a[k+NN]<=x)
					k+=NN;
			}
			
			if(a[k]==x) fprintf(g,"%d\n",k);
			else fprintf(g,"-1\n");
		}
		else if(p==1)
		{
			k=0;
			for(NN=N;NN;NN>>=1)
			{
				if(k+NN<=n && a[k+NN]<=x) k+=NN;
			}
			NN<<=1;
			k-=NN;
			fprintf(g,"%d\n",k);
		}
			
		
		else 
		{
			k=n;
			for(NN=N;NN;NN>>=1)
			{
				if(k-NN>0 && a[k-NN]>=x)
					k-=NN;
			}
			fprintf(g,"%d\n",k);
		}
	}
	fclose(f);
	fclose(g);
	return 0;
}