#include <stdio.h>
#include <stdlib.h>
int v[100001];
int main()
{
    FILE *fin, *fout;
    int m, n, e, c, i;
    long long st, dr, mij;
    fin = fopen ("cautbin.in", "r");
    fout = fopen ("cautbin.out", "w");
    fscanf (fin, "%d", &n);
    for (i = 1; i <= n; i++){
      fscanf (fin, "%d", &v[i]);
    }
    fscanf (fin, "%d", &m);
    for (i = 0; i < m; i++){
      fscanf (fin, "%d%d", &c, &e);
      if (c == 0){
        st = 1;
        dr = n + 1;
        while (dr - st > 1){
          mij = (dr + st) / 2;
          if (v[mij] > e)
            dr = mij;
          else
            st = mij;
        }
        if (v[st] != e)
          st = -1;
      }else if (c == 1){
        st = 1;
        dr = n + 1;
        while (dr - st > 1){
          mij = (dr + st) / 2;
          if (v[mij] > e)
            dr = mij;
          else
            st = mij;
        }
      }else{
        st = 1;
        dr = n + 1;
        while (dr - st > 1){
          mij = (dr + st) / 2;
          if (v[mij] >= e)
            dr = mij;
          else
            st = mij;
        }
        st = dr;
      }
      fprintf (fout, "%d\n", st);
    }
    return 0;
}