#include <stdio.h>
#define DIM 5001

int v[DIM];
int n,i,tip,x,m;

  FILE *f = fopen("cautbin.in", "r");
  FILE *g = fopen("cautbin.out", "w");

int tip0(int x) {
  int p,u,poz,m;
  p = 1;
  u = n;
  poz = -1;

  while (p<=u) {
    m = p + (u-p)/2;

    if (v[m]==x)
      if (m > poz)
	poz = m;

    if (x < v[m])
      u = m-1;
    else
      p = m+1;
  }
  return poz;
}

int tip1(int x) {
  int p,u,poz,m;
  p = 1;
  u = n;

  while (p<=u) {
    m = p + (u-p)/2;

    if (v[m] <= x) {
      poz = m;
      p = m+1;
    }
    else
      u = m-1;
  }

  return poz;
}

int tip2(int x) {
  int p,u,poz,m;
  p = 1;
  u = n;

  while (p<=u) {
    m = p + (u-p)/2;

    if (v[m] >= x) {
      poz = m;
      u = m-1;
    }
    else
      p = m+1;
  }

  return poz;
}

int main(){

  fscanf(f,"%d",&n);

  for (i=1; i<=n; i++)
    fscanf(f,"%d",&v[i]);

  fscanf(f,"%d",&m);

  for (i=1; i<=m; i++) {
    fscanf(f,"%d %d",&tip,&x);

    if (tip==0)
      fprintf(g,"%d\n",tip0(x));
    if (tip==1)
      fprintf(g,"%d\n",tip1(x));
    if (tip==2)
      fprintf(g,"%d\n",tip2(x));

  }

  fclose(f);
  fclose(g);

  return 0;
}