#include <stdio.h>
int v[100000];
int n;
int caut0(int x){
  int i, pas;
  i=0;
  pas=1<<16;
  while(pas!=0){
    if(i+pas<=n && v[i+pas]<=x)
      i=i+pas;
    pas=pas/2;
  }
  if(v[i]!=x)
    return -1;
  return i;
}
int caut1(int x){
  int i, pas;
  i=0;
  pas=1<<16;
  while(pas!=0){
    if(i+pas<=n && v[i+pas]<=x)
      i=i+pas;
    pas=pas/2;
  }
  return i;
}
int caut2 (int x){
  int i, pas;
  i=0;
  pas=1<<16;
  while(pas!=0){
    if(i+pas<=n && v[i+pas]<x)
      i=i+pas;
    pas=pas/2;
  }
  return i;
}
int main(){
  FILE *fin, *fout;
  fin=fopen("cautbin.in", "r");
  fout=fopen("cautbin.out", "w");
  int  m, i, x, val;
  fscanf(fin, "%d", &n);
  for(i=1;i<=n;i++)
    fscanf(fin, "%d", &v[i]);
  fscanf(fin, "%d", &m);
  for(i=1;i<=m;i++){
    fscanf(fin, "%d%d", &x, &val);
    if(x==0)
      fprintf(fout, "%d ", caut0(val));
    if(x==1)
      fprintf(fout, "%d ", caut1(val));
    if(x==2)
      fprintf(fout, "%d ", caut2(val)+1);
  }
    return 0;







}