#include<fstream.h>

long l,r,m,i,n,a[100001],gasit,x,op,mm;

int main()
{
 ifstream f("cautbin.in");
 ofstream g("cautbin.out");
 f>>n;
 for(i=1;i<=n;i++)f>>a[i];
 f>>mm;
 for(i=1;i<=mm;i++)
 {
  f>>op>>x;
  if(!op)
   {
    l=1;r=n;gasit=0;
    while(l<=r&&!gasit)
     { 
      m=l+((r-l)>>1);
      if(a[m]==x)gasit=1;
      else if(a[m]>x) r=m-1;
      else l=m+1;
      }
    if(!gasit)g<<"-1";
    else
     {
      while(a[m]==x)m++;
      g<<m-1<<'\n';
      }
    }
  else if(op==1)
	{
	 l=1;r=n;
	 while(l<r)
	 {
	  m=l+((r-l)>>1);
	  if(a[m]<=x)l=m+1;
	  else r=m-1;
	  }
	while(a[m]>x)m--;
	g<<m<<'\n';
	}
       else
	{
	 l=1;r=n;
	 while(l<r)
	 {
	  m=l+((r-l)>>1);
	  if(a[m]>=x)r=m-1;
	  else l=m+1;
	  }
	 while(a[m]<x)m++;;
	 g<<m<<'\n';
	 }
   }
 return 0;
 }