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

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

long caut_bin(long i,long s,long x)
  {long 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()   
    {long h,m,i,solutie,y;   
    FILE*f=fopen ("cautbin.in","r");   
    FILE*g=fopen ("cautbin.out","w");   
     fscanf(f,"%ld",&n);    
     for(i=1;i<=n;i++)   
         fscanf(f,"%ld",&a[i]);   
     fscanf(f,"%ld",&m);   
     for(i=1;i<=m;i++)   
         {fscanf(f,"%ld%ld",&h,&x);    
          if(h==0) 
			   {y=caut_bin(1,n,x);
		        if(a[1]>x) solutie=-1;
		          else if(a[1]==x) solutie=1;
				    else if(a[n]==x) solutie=n;
				      else if(a[n]<x) solutie=-1;
				        else 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,"%ld\n",solutie);   
          }   
      fclose(f);   
      fclose(g);           
      return 0;   
    }