#include <stdio.h>
#include <stdlib.h>
long long 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;
        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++;
    else if(c==2 && v[mij]==x)
      while(v[mij-1]==x) mij--;
    if(v[mij]!=x){
      if(c==0) mij=-1;
      else if(c==1) mij=dr;
      else mij=st;
    }
    fprintf(fout, "%d\n", mij);
  }
  fclose(fin);
  fclose(fout);
    return 0;
}