#include<fstream>
#define dim 100001
using namespace std;
unsigned long a[dim];
int main()
{unsigned long n,m,i,nr,poz=0,man,j;

 ifstream f("cautbin.in");
 ofstream g("cautbin.out");
f>>n;
 for(i=1;i<=n;i++)
   f>>a[i];
f>>m;
for(j=1;j<=m;j++)
  {f>>man>>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) g<<"-1"<<'\n';
      else g<<poz<<'\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: g<<poz<<'\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: g<<poz<<'\n';	  
   
	 }}
f.close();
g.close();
return 0;
}