#include<fstream>   
//#define dim 100001   
using namespace std;   
long long a[100001];   
int main()   
{unsigned int n,m,nr,i,j,poz;
long long nr;
int x,ok=0;   
  ifstream f("cautbin.in");   
  ofstream g("cautbin.out");   
 f>>n;   
  for(i=1;i<=n;i++)   
   f>>a[i];   
 f>>m;   
   for(i=1;i<=m;i++)   
  {f>>x>>nr; j=0; ok=0;   
    if(a[n/2]<nr)   
     {j=n/2;   
      while(a[j]<=nr)   
      {j++; poz=j;}}   
    if(a[n/2]>nr)   
        while(a[j]<=nr)   
          {j++; poz=j;}   
    if(a[n/2]==nr) poz=n/2;      
          
    if(a[poz]==nr)   
      ok=1;   
      
   if((x==0)&&(ok==1)) g<<poz<<'\n';   
   if((x==0)&&(ok==0)) g<<"-1"<<'\n';   
      
   if((x==1)&&(ok==0)) g<<poz-1<<'\n';   
   if((x==1)&&(ok==1)) g<<poz<<'\n';   
      
   if(x==2) g<<poz<<'\n';}   
  
f.close();     
g.close();   
return 0;   
}