#include <stdio.h>
#include <stdlib.h>
int v[100000];

int binSearch(int lengthOfVector, int target) {
    int st = -1;
    int dr = lengthOfVector - 1;
    int mij;
    while (dr - st > 1) {
      mij = (st + dr) / 2;
      if (v[mij] >= target) {
        dr = mij;
      } else {
        st = mij;
      }
    }

    if (v[dr] == target){
      //printf("%d apare in sir pe pozitia %d\n", target, dr);
      return dr;
    } else {
      //printf("%d NU apare in sir pe pozitia %d\n", target, dr);
      return -1;
    }

}
int main()
{
    FILE *fin = fopen("cautbin.in", "r");
    FILE *fout = fopen("cautbin.out", "w");
    int c, x, n, m;
    fscanf(fin, "%d", &n);
    for (int i = 0; i < n; i++) {
      fscanf(fin, "%d", &v[i]);
    }
    fscanf(fin, "%d", &m);
    for (int _ = 0; _ < m; _++) {
        fscanf(fin, "%d %d", &c, &x);
        int idx = binSearch(n, x);
        if (c == 0) {
            //printf("[C = 1]\n");
            while (v[idx] == x) {
                //printf(" [C = 1] %d %d\n", idx, x);
                idx += 1;
            }
            fprintf(fout, "%d\n", idx);
        //printf("\n");
        } else if (c == 1) {
            if (idx == -1) {
                while (idx == -1) {
                    x -= 1;
                    idx = binSearch(n, x);
                    //printf("%d here", idx);
                }
            }
            while (v[idx] == x) {
                //printf("%d", idx);
                idx += 1;
            }
            fprintf(fout, "%d\n", idx);

        } else {
            if (idx == -1) {
                while (idx == -1) {
                    x += 1;
                    idx = binSearch(n, x);
                    //printf("%d %d", idx, x);
                }
            }
            while (v[idx] == x) {
                idx -= 1;
                //printf("%d %d", idx, x);
            }
            fprintf(fout, "%d\n", idx+2);
        }
    }

    return 0;
}