#include <stdio.h>
#define NMAX 100005
int n,v[NMAX];

int find(int x)
{
 int st=1,dr=n,poz=-1;
 while (st<dr)
  {
   int mij=st+(dr-st)/2;
   if (v[mij]<=x)
      {
       if (v[mij]==x)poz=mij;
       st=mij+1;
      }
      else
     {dr=mij-1;}
  }
 if (st==dr&&v[st]==x) return st;
 return poz;
}

int find2(int x)
{
 int st=1,dr=n,poz=0;
 while (st<dr)
  {
   int mij=st+(dr-st)/2;
   if (v[mij]>x)dr=mij-1;
      else
       {
	poz=mij;
	st=mij+1;
       }
  }
 return poz;
}

int find3(int x)
{
 int st=1,dr=n,poz=0;
 while (st<dr)
  {
   int mij=st+(dr-st)/2;
   if (v[mij]<x) st=mij+1;
      else
       {
	poz=mij;
	dr=mij-1;
       }
  }
 return poz;
}

int main()
{
 FILE *fin=fopen("cautbin.in","r");
 FILE *fout=fopen("cautbin.out","w");
 fscanf(fin,"%d",&n);
 int i,m,op;
 for (i=1;i<=n;++i)
  fscanf(fin,"%d",&v[i]);
 fscanf(fin,"%d",&m);
 while (m--)
  { int x;
   fscanf(fin,"%d %d",&op,&x);
   switch (op)
    {
     case 0: { fprintf(fout,"%d\n",find(x)); break;}
     case 1: { fprintf(fout,"%d\n",find2(x)); break;}
     default : { fprintf(fout,"%d\n",find3(x));}
    }
  }
 fcloseall();
 return 0;
}