# include <stdio.h>
long n,M,p,u,poz,m,x,tip,i;
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%ld",&tip,&x);
    if (tip==0) {
      p=1;
      u=n;
      poz=-1;
      while (p<=u) {
	m=p+(u-p)/2;
	if (x==v[m])
	  if (m>poz)
	    poz=m;
	if (x<v[m])
	  u=m-1;
	else
	  p=m+1;
      }
      if (poz)
	fprintf(g,"%ld\n",poz);
      else
	fprintf(g,"-1");
    }

    if (tip==1) {
      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;
      }
      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;
	  u=m-1;
	}
	else
	  p=m+1;
      }
      fprintf(g,"%ld\n",poz);
    }
  }
  fclose(f);
  fclose(g);
  return 0;
}