#include<fstream>
#define dim 100001
using namespace std;
unsigned int a[dim];
int main()
{unsigned int n,m,nr,i,j,poz;
int x;
  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++)
  {poz=0;
   f>>x>>nr; 
    if(x==0)
	{ if(a[n/2]==nr) {poz=n/2; g<<poz<<'\n';}
      if(a[n/2]<nr) 
       for(i=n/2;i<=n;i++)
        if(a[i]==nr) {poz=i; g<<poz<<'\n'; break;}
      
	  if(a[n/2]>nr)
       for(i=n/2;i>=1;i--)
        if(a[i]==nr) {poz=i; g<<poz<<'\n'; break;}
	  if(poz==0) g<<-1<<'\n';
    }
   
    if(x==2)
	{if(a[n/2]<nr)
	 for(i=n/2;i<=n-1;i++)
       if((a[i]<=nr)&&(a[i+1]>nr)) {poz=i+1; break;}
    
    
     if(a[n/2]>nr)
      for(i=1;i<=n/2-1;i++)
        if((a[i]<=nr)&&(a[i+1]>nr)) {poz=i+1; break;}
    if(a[n/2]==nr) g<<n/2<<'\n';
	else g<<poz<<'\n';
	}
	
	if(x==1)
	{if(a[n/2]<nr)
	 for(i=n/2;i<=n-1;i++)
       if((a[i]<=nr)&&(a[i+1]>nr)) {poz=i; break;}
    
    
     if(a[n/2]>nr)
      for(i=1;i<=n/2-1;i++)
        if((a[i]<=nr)&&(a[i+1]>nr)) {poz=i; break;}
    if(a[n/2]==nr) g<<n/2<<'\n';
	else g<<poz<<'\n';
	}
   }  
	
f.close();  
g.close();
return 0;
}