#include<stdio.h>
#define M 100010

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

long n,m;
long v[M];

long c(int x,long y)
{
	long i,j,m,p,q;
	int ok=1;
	
	i=1;
	j=n;
	while(i<=j && ok)
	{
		m=(i+j)/2;
		if(v[m]==y) ok=0;
		else if(v[m]>y) {if(x==2) p=m;
		                 j=m-1;} 
		     else {if(x==1) q=m;
			       i=m+1;}
	}
	
	if(x==0) if(ok==0) {for(i=m;i<=n;i++)
		                   if(v[i]==y) m=i;
	                       else break;
                        return m;
	                     }						 
	         else return -1;
	
	if(x==1) if(ok==0) {for(i=m;i<=n;i++)
		                  if(v[i]!=y) return i-1;
	                      }
	         else return q;
	
	if(x==2) if(ok==0) {for(i=m;i>=1;i--)
		                  if(v[i]!=y) return i+1;
	                    }
	         else return p;
	}
	
int main()
{
	long y,i;
	int x;
	
	fscanf(f,"%ld",&n);
	
	for(i=1;i<=n;i++)
		fscanf(f,"%ld",&v[i]);
	
	fscanf(f,"%ld",&m);
	
	for(i=1;i<=m;i++)
	{
		fscanf(f,"%d%ld",&x,&y);
		fprintf(g,"%ld\n",c(x,y));
	}
	
	fclose(f);
	fclose(g);
	return 0;
}