#include <cstdio>
using namespace std;
#define nmax 100001
#define md ((l+r)>>1)
FILE *f=fopen("cautbin.in","r");
FILE *g=fopen("cautbin.out","w");
int n,m;
int A[nmax];
int cbin1(int tip,int val)
 {
 int l,r;
 l=1;
 r=n;
 while(l<=r)
  {
  if(A[md]==val)
   {
   if(A[md+1]!=val)
	return md;
   else
    l=md+1;
   continue;
   }
  if(A[md]>val)
   {
   r=md-1;
   continue;
   }
  else
   l=md+1;
  }
 return -1;
 }
int cbin2(int tip,int val)
 {
 int l,r,pz;
 pz=-1;
 l=1;
 r=n;
 while(l<=r)
  {
  if(A[md]<=val)
   { 
   pz=md;
   l=md+1;
   }
  else
   {
   r=md-1;
   }
  }
 return pz;
 }
int cbin3(int tip,int val)
 {
 int l,r,pz;
 pz=-1;
 l=1;
 r=n;
 while(l<=r)
  {
  if(A[md]>=val)
   {
   pz=md;
   r=md-1;
   }
  else
   {
   l=md+1;
   }
  }
 return pz;
 }
int main()
 {
 int i,tip,val;
 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",&tip,&val);
  if(tip==0)
   fprintf(g,"%d\n",cbin1(tip,val));
  else if(tip==1)
   fprintf(g,"%d\n",cbin2(tip,val));
  else
   fprintf(g,"%d\n",cbin3(tip,val));
  }
 return 0;
 }