#include<stdio.h>
#define dim 100001
int s[dim];
using namespace std;
int main()
{short int q;
int nr,i,n,m,mij,j;
FILE *f=fopen("cautbin.in","r"), *g=fopen("cautbin.out","w");

fscanf(f,"%d",&n);
 for(i=1;i<=n;i++) fscanf(f,"%d",&s[i]);

 mij=s[n/2];
 
fscanf(f,"%d",&m);
 for(i=1;i<=m;i++)
 {fscanf(f,"%hd%d",&q,&nr);
   if(q==0)
	{if(mij==nr) fprintf(g,"%d\n",n/2);
	 if(mij>nr)
        for(j=1;j<mij;j++) {if(s[j]==nr) {fprintf(g,"%d\n",j); break;}
		                    if(s[j]>nr)  {fprintf(g,"-1\n"); break;}
							}
     if(mij<nr)
		for(j=mij;j<=n;j++) {
			           if(s[j]==nr) 
		                 {fprintf(g,"%d\n",j); break;}
		                       if(s[j]>nr)  {fprintf(g,"-1\n"); break;}
							  }
	}

   if(q==1)
     {if(s[n]<nr) {fprintf(g,"%d\n",n); goto pas;}
	 if(mij<nr)
	   for(j=mij+1;j<=n;j++) {if(s[j]>nr) {fprintf(g,"%d\n",j-1); break;} 
	                          }
	 if(mij>nr)
	   for(j=1;j<=mij;j++) {if(s[j]>nr) {fprintf(g,"%d\n",j-1); break;} }
	 pas:if(mij==nr) fprintf(g,"%d\n",n/2); 
	   } 
	 
	
   if(q==2)
   {if(s[n]==nr) {fprintf(g,"%d\n",n); goto pass;}
	if(mij<nr)
	   for(j=mij+1;j<=n;j++) {if(s[j]>=nr) {fprintf(g,"%d\n",j); break;} }
	if(mij>nr)
	   for(j=1;j<=mij;j++) {if(s[j]>=nr) {fprintf(g,"%d\n",j); break;} }
	 pass: if(mij==nr) fprintf(g,"%d\n",n/2); }}
fclose(f);
fclose(g);
return 0;
}