#include <stdio.h>
#include <stdlib.h>

#define MAXN 100000

int v[MAXN];
int main(){
  FILE*fin=fopen("cautbin.in", "r");
  FILE*fout=fopen("cautbin.out", "w");
  int n, dr, st, i, ok, e, m, mij, x;
  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, &e);
    st=0;
    dr=n+1;
    ok=1;
    if(x==0){
      while(dr-st>1) {
        mij=(st+dr)/2;
        if (v[mij]<=e)
          st=mij;
        else
          dr=mij;

        if(v[mij]==e)
          ok=0;
      }
      mij=(dr+st)/2;
      if(ok==1)
        fprintf(fout, "-1");
      else
        fprintf(fout, "%d\n", mij);
    }
    if(x==1){
      while(dr-st>1) {
        mij=(st+dr)/2;
        if (v[mij]<=e)
          st=mij;
        else
          dr=mij;
      }
      fprintf(fout, "%d\n", st);
    }
    if(x==2){
      while(dr-st>1) {
        mij=(st+dr)/2;
        if (v[mij]>=e)
          dr=mij;
        else
          st=mij;
      }
      fprintf(fout, "%d\n", dr);
    }
  }
  return 0;
}