#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;
    while(st<=dr){
        mij=(st+dr)/2;
        if(x==v[mij]) st=dr+1;///daca gasim oprim cautarea
        else 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
      }
    if(c<2)
      while(v[mij+1]==x) mij++;///mergem cat mai in dreapta
    else if(c==2)
      while(v[mij-1]==x) mij--;///mergem cat mai in stanga
    if(v[mij]!=x){
      if(c==0) mij=-1;///daca mijlocul la care s-a oprit nu e bun nu se gaseste elemntul
      else if(c==1) mij=dr;///daca mijlocul la care ne-am oprit nu e elementul e clar ca limita dreapta a coborat la elementul mai mic
      else mij=st;///daca mijlocul la care ne-am oprit nu e bun, e clar ca limita stanga s-a dusdus la elementul mai mare
    }
    fprintf(fout, "%d\n", mij);
  }
  fclose(fin);
  fclose(fout);
    return 0;
}