# include <stdio.h>

long i,n,p,u,m,x,M,tip,j,pmax;

int v[100002];

int main() {

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

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

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

  fscanf(f,"%ld",&M);

  for (i=1;i<=M;i++) {

    fscanf(f,"%ld",&tip);
    fscanf(f,"%ld",&x);

    if (tip==0) {
      p=1;
      u=n;
      pmax =-1;
      while (p<=u) {
	m=p+(u-p)/2;
	if (x==v[m])
	  if (m>pmax)
	    pmax=m;
	if (x>v[m])
	  p=m+1;
	else
	  u=m-1;
      }
      fprintf(g,"%ld\n",pmax);
    }

    if (tip==1) {

      p=1;
      u=n;

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

	if (x<=v[m]) {
	  poz = m;
	  u = m-1;
	} else {
	  p = m+1;
	}
      }
      fprintf(g,"%ld\n",poz);
    }

    if (tip==2) {
      p=1;
      u=n;
      while (p<=u) {
	m=p+(u-p)/2;
	if (x>=v[m]) {
	  poz = m;
	  p=m+1;
	}
	else
	  u=m-1;
      }

      fprintf(g,"%ld\n",poz);
    }
  }

  fclose(f);
  fclose(g);

  return 0;
}