#include<stdio.h>
#define dim 100001
using namespace std;

int a[dim],x,n,i,s;

int caut_bin(int i,int s,int x)
  {int mij;
  mij=(i+s)/2;
  if(i>s) return i;
   if(a[mij]==x) return mij;   
      else if(a[mij]<x) return caut_bin(mij+1,s,x);
          else return caut_bin(i,mij-1,x);	  
   }	  
int main()   
    {int h,m,i,solutie,y;   
    FILE*f=fopen ("cautbin.in","r");   
    FILE*g=fopen ("cautbin.out","w");   
     fscanf(f,"%d",&n);    
     for(i=1;i<=n;i++)   
         fscanf(f,"%d",&a[i]);   
     fscanf(f,"%d",&m);   
     for(i=1;i<=m;i++)   
         {fscanf(f,"%d%d",&h,&x);    
          if(h==0) 
			   {y=caut_bin(1,n,x);
		        if(a[y]==x) solutie=y;
				  else solutie=-1;
			   }				  
            else if(h==1) 
			     {y=caut_bin(1,n,x);
				  if(a[y-1]==x) solutie=y+1;
				    else while(a[y]<=x&&y<=n) ++y;
				   solutie=--y; 
			      }				
              else if(h==2) 
			       {y=caut_bin(1,n,x);
			        if(a[y-1]==x) solutie=y;
					  else while(a[y]>=x&&y>0) y--;
					solutie=++y;	   
			        } 
			   fprintf(g,"%d\n",solutie);   
          }   
      fclose(f);   
      fclose(g);           
      return 0;   
    }