#include <stdio.h>
#include <stdlib.h>
int v[100000];
int main(){
  FILE *fin, *fout;
  fin=fopen("cautbin.in", "r");
  fout=fopen("cautbin.out", "w");
  int i, n, m, c, x, dr, st, mij;
  fscanf(fin, "%d", &n);
  for(i=1; i<=n; i++)
    fscanf(fin, "%d", &v[i]);
  fscanf(fin, "%d", &m);
  while(m--){
    fscanf(fin, "%d%d", &c, &x);
    st=1; dr=n;
    if(c<2){
      while(st<=dr){
          mij=(st+dr)/2;
          if(x<v[mij]) dr=mij-1;///daca e mai mic strict micsoram bariera dreapta
          else st=mij+1;///daca e mai mare se mareste bariera stamga, dar daca e egal tot marim bariera stanga
      }
      mij=st-1;
      if(c==0 && (v[st-1]!=x || st==1))
        mij=-1;
    }
    else {
      while(st<=dr){
          mij=(st+dr)/2;
          if(x<=v[mij]) dr=mij-1;///daca e mai mic strict micsoram bariera dreapta, daca e egal tot micsoram bariera dreapta
          else st=mij+1;///daca e mai mare se mareste bariera stanga
      }
      mij=st;
    }
    fprintf(fout, "%d\n", mij);
  }
  fclose(fin);
  fclose(fout);
    return 0;
}