#include<fstream.h>
#define dim 100002


unsigned long v[dim],jum,x,n,m,i,nr,poz;

ifstream f("cautbin.in");
ofstream g("cautbin.out");


int caut0(int li, int ls)
{
 jum=(li+ls)/2;

 if(v[jum]<x)
  {
   if(v[jum+1]>x) return -1;

   if(v[jum+1]==x)
     {
      jum++;

      while(v[jum]==x) jum++;

      return jum-1;
     }

   return caut0(jum+1,n);
  }

 if(v[jum]>x)
  {
   if(v[jum-1]<x) return -1;

   if(v[jum-1]==x) return jum-1;

   return caut0(li,jum);
  }

 if(v[jum]==x) return jum;

}


//stanga
int caut1(int li, int ls)
{
 jum=(li+ls)/2;

 if(v[jum]<x) //return
   {
    if(v[jum+1]==x)
     {
      jum++;
      while(v[jum]==x) jum++;
      return jum-1;
     }

    if(v[jum+1]>x) return jum;

    caut1(jum+1,n);
   }

   else if(v[jum]>x)
	  {
	   if(v[jum-1]<=x) return jum-1;

	   caut1(li,jum);
	  }
//return 0;
}

//dreapta
int caut2(int li, int ls)
{
 jum=(li+ls)/2;

 if(v[jum]>x)
  {
   if(v[jum-1]==x)
    {
     jum--;
     while(v[jum]==x) jum--;

     return jum+1;
    }

   if(v[jum-1]<x) return jum;
   caut2(li,jum);
  }

   else if(v[jum]<x)
	  {
	   if(v[jum+1]>=x) return jum+1;

	   caut2(jum+1,n);
	  }
//return 0;
}

int main()
{

f>>n;
for(i=1;i<=n;i++) f>>v[i];
n++;
v[n]=4000000000;

f>>m;
for(i=1;i<=m;i++)
 {
  f>>nr>>x;

  if(nr==0)
    g<<caut0(1,n)<<'\n';

   else if(nr==1) g<<caut1(1,n)<<'\n';

     else g<<caut2(1,n)<<'\n';
 }


return 0;
}