#include<fstream>
using namespace std;
   int a[100005], n,i,j,ls,li=1,mij,aux=0,x,y,gasit=0,M;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int catbin0(int nr)
{ gasit=0;
      while(li<=ls&&!gasit)
                
                  {   mij=(li+ls)/2;
                     if(a[mij]>nr)
                     ls=mij;
                     else if(a[mij]<nr)li=mij;
                     else 
                     gasit=1;
                     }
                     
                     if (gasit==1) {while(a[mij+1]==nr) mij++;return mij;}
                     else return -1;
                     
                  
             
              
            
            
            }
int catbin1(int nr)
{ gasit=0;
      while(li<=ls&&!gasit)
                
                  {   mij=(li+ls)/2;
                     if(a[mij]>nr)
                     li=mij;
                     else if(a[mij]<nr)li=mij;
                     else 
                     gasit=1;
                    
                    
                     
                     }
                     if(gasit=1)
                    return mij;
                    else catbin1(nr--);
                   
                                  
            
            }
int catbin2(int nr)
{ gasit=0;
      while(li<=ls&&!gasit)
                
                  {   mij=(li+ls)/2;
                     if(a[mij]>nr)
                     li=mij;
                     else if(a[mij]<nr)li=mij;
                     else 
                     gasit=1;
                     }
                     
                     if(gasit=1)
                    return mij;
                    else catbin1(nr++);
            
            }
/*0 x - cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir
1 x - cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x
2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x*/



int main()
{
     cin>>n;ls=n;
     for(i=1;i<=n;i++)cin>>a[i];
         
                     cin>>M;
                    for(i=1;i<=M;i++)
                     {          cin>>x>>y;
                                if(x==0)
                               cout<< catbin0(y);
                                if(x==1)
                                 cout<<  catbin1(y);
                                   if(x==2)
                                  cout<<     catbin2(y);
                                                                                           
                                
                                }              
    return 0;
       
    
    
    
    }