#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 cb1(long i, long j,long y)
{
	if(i<=j) {long m=(i+j)/2;
	
	          if(y>v[m]) return cb1(m+1,j,y);
	          else if(y<v[m]) return cb1(i,m-1,y);
	               else {int q;
	                     for(q=m;q<=j;q++)
				             if(y!=v[q]) return q-1;
		                }
	           }
	return -1;
}

long p;

long cb2(long i, long j, long y)
{
	if(i<=j) {long m=(i+j)/2;
	     
	          if(y>v[m]) return cb2(m+1,j,y);
	          else if(y<v[m]) {p=m;
			                   return cb2(i,m-1,y);}
			       else {long q;
				         for(q=m;q<=j;q++)
							 if(y!=v[q]) return q-1;
				         }
	         }
	return p;
}
	
long cb3(long i,long j, long y)
{
	if(i<=j) {long m=(i+j)/2;
	       
	          if(y>v[m]) {p=m;
	                      return cb3(m+1,j,y);}
			  else if(y<v[m]) return cb3(i,m-1,y);
			       else {long q;
			             for(q=m;q>=i;q--)
							 if(v[q]!=y) return q+1;
				        }
	          }
	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);
		
		if(x==0) fprintf(g,"%ld\n",cb1(1,n,y));
		else if(x==1) fprintf(g,"%ld\n",cb2(1,n,y));
		     else fprintf(g,"%ld\n",cb3(1,n,y));
		         
	}
	
	fclose(f);
	fclose(g);
	return 0;
}