#include<fstream>
#include<iostream>
using namespace std;


int a[100000], n, li, ls, gasit, k, mij,i, m,x,op;

int cautare0(int x)
{
    gasit=0;
    li=1;ls=n;
    
    while(li<ls)
    {
      mij=(li+ls)/2;
      
      if(x==a[mij])
         {
          gasit=1;
          break;
         }
      else if(x<a[mij])
             ls=mij;
      else li=mij+1;
     }
     
   if(gasit)
     {
       k=1;
       while(a[mij+k]==a[mij])
          k++;
       
       return mij+k-1;
       }
   else
     return -1;
}

  int cautare1(int x)
{
    li=1;ls=n;
    
    while(li<ls)
    {
      mij=(li+ls)/2;
      
      if(a[mij]<=x)
             li=mij+1;
      else ls=mij;
     }
     

       k=1;
       while(a[mij+k]==a[mij])
          k++;
       
       return mij+k-1;
            
}  
    
  int cautare2(int x)
{
  
    li=1;ls=n;
    
    while(li<ls)
    {
      mij=(li+ls)/2;
      
      if(a[mij]>=x)
             ls=mij;
      else li=mij+1;
     }
     

       return mij+1;
     
}
   
int main()
{
    ofstream g("cautbin.out");
    
    ifstream f("cautbin.in");
         f>>n;
      for(i=1;i<=n;i++)
         f>>a[i];
       f>>m;
    for(i=1;i<=m;i++)
    {
       f>>op>>x;
         if(op==0)
           g<<cautare0(x)<<"\n";
        else if(op==1)
           g<<cautare1(x)<<"\n";
        else g<<cautare2(x);
           
    }

return 0;

}