#include <stdio.h>
#define Nmax 100001

int n, t, T[Nmax];
int bin_0 (int x);
int bin_1 (int x);
int bin_2 (int x);

int main()
{
  int i, tip, val;
  FILE *fin=fopen("cautbin.in", "r");
  FILE *fout=fopen("cautbin.out", "w");
  fscanf (fin, "%d\n", &n);
  for (i=1; i<=n; i++)
    fscanf (fin, "%d ", &T[i]);
  fscanf (fin, "%d\n", &t);
  for (i=0; i<t; i++)
    {
      fscanf (fin, "%d %d\n", &tip, &val);
      if (tip==0)
	fprintf (fout, "%d\n", bin_0(val));
      if (tip==1)
	fprintf (fout, "%d\n", bin_1(val));
      if (tip==2)
	fprintf (fout, "%d\n", bin_2(val));
    }
  return 0;
}

int bin_0 (int x)
{
  int m, st, dr;
  st=1; dr=n;
  while (st<=dr)
    {
       m=st+(dr-st)/2;
       if (T[m]==x)
	 return m;
       else
	 if (T[m]>x)
	   dr=m-1;
	 else
	   st=m+1;
    }
  return -1;
}

int bin_1 (int x)
{
  int m, st, dr, poz;
  st=1; dr=n;
  while (st<=dr)
    {
      m=st+(dr-st)/2;
      if (T[m]<=x)
	{
	  poz=m;
	  st=m+1;
	}
      else
	dr=m-1;
    }
  return poz;
}

int bin_2 (int x)
{
  int m, st, dr, poz;
  st=1; dr=n;
  while (st<=dr)
    {
      m=st+(dr-st)/2;
      if (T[m]>=x)
	{
	  poz=m;
	  dr=m-1;
	}
      else
	st=m+1;
    }
  return poz;
}