#include<stdio.h>
#define dim 100001
using namespace std;
int a[dim];
int main()
{int n,m,i,nr,poz=0,man,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",&a[i]);
fscanf(f,"%d",&m);
for(j=1;j<=m;j++)
  {fscanf(f,"%d",&man); fscanf(f,"%d",&nr); poz=0;
	if(man==0)
	{
	  if(a[n/2]<nr) 
        for(i=n/2+1;i<=n;i++)
          if(a[i]==nr) poz=i; 
       
	  if(a[n/2]>nr)
        for(i=n/2;i>=1;i--)
           if(a[i]==nr) poz=i;
		
	  if(a[n/2]==nr)
	    poz=n/2;
		
	  if(poz==0) {fprintf(g,"%d","-1"); fprintf(g,"\n");}
      else {fprintf(g,"%d",poz); fprintf(g,"\n");}
    }
    
	if(man==1)
   	 {if((a[1]<=nr)&&(a[2]>nr)) {poz=1; goto pas;}
      if(a[n]<=nr) {poz=n; goto pas;}
       
      if(a[n/2]==nr) poz=n/2;
      
      if(a[n/2]<nr)
	  for(i=n/2;i<=n;i++)
         {if(a[i]>nr) {poz=i-1; break;}
          if(a[i]==nr) {poz=i; break;}
		 }

      if(a[n/2]>nr)
    	for(i=1;i<=n/2;i++)
		{if(a[i]>nr) {poz=i-1;break;}
         if(a[i]==nr) {poz=i; break;}
        }
      pas: fprintf(g,"%d",poz); fprintf(g,"\n");
	 }


	if(man==2)
	{if(a[1]>=nr) {poz=1; goto pas2;}
     
     if(a[n/2]==nr) poz=n/2;

     if(a[n/2]<nr)
        for(i=n/2;i<=n;i++)
          if(a[i]>=nr) {poz=i; break;}
   
     if(a[n/2]>nr)
        for(i=n/2;i>=1;i--)
          {if(a[i]<nr) {poz=i+1;break;}
           if(a[i]==nr) {poz=i; break;}
		  }
		  
	pas2: fprintf(g,"%d",poz); fprintf(g,"\n");	
   
	 }}
fclose(f);
fclose(g);
return 0;
}