#include<fstream>

using namespace std;

int main() 
{ int v[100002], N, M, caz, x, mid, poz, st, dr;

fstream f("cautbin.in", ios::in);
fstream g("cautbin.out", ios::out);

f>>N;
for(int i=1;i<=N;i++)
f>>v[i];

f>>M;
for(int i=1;i<=M;i++){
 f>>caz>>x; dr=N; st=1;
 
    if(caz==0) 
{ while(st<=dr)
   {mid=st+(dr-st)/2;
   if(v[mid]>x)   
     dr=mid-1;        
    else  
     st=mid+1; }
  poz=st+(dr-st)/2;
  if(v[poz]>x) poz--;
if(v[poz]==x)g<<poz<<endl;   
else  g<<"-1"<<endl;}     
                           
     if(caz==1) 
{ while(st<=dr)
   {mid=st+(dr-st)/2;
   if(v[mid]<=x)
     {poz=mid; st=mid+1; }
   else dr=mid-1;}
  g<<poz<<endl; }
 
    if(caz==2) 
{ while(st<=dr)
  {mid=st+(dr-st)/2;
   if(v[mid]>=x && poz>mid)
     { poz=mid; dr=mid-1;}
   else 
     if(v[mid]>=x) dr=mid-1;
     else if(v[mid]<x) st=mid+1;}
g<<poz<<endl; }
}

f.close();
g.close();
return 0;
}