#include <stdio.h>
#define NMAX 100000

using namespace std;

FILE* fin, * fout;
int n, m, v[NMAX];

int type0(int x) {
    int i = 0, j = n - 1;
    while (i <= j) {
        int m = i + (j - i) / 2;
        if (v[m] == x && (m == n - 1 || v[m + 1] != x))
            return m + 1;
        if (v[m] <= x)
            i = m + 1;
        else
            j = m - 1;
    }
    return -1;
}

int type1(int x) {
    int i = 0, j = n - 1;
    while (i <= j) {
        int m = i + (j - i) / 2;
        if (v[m] <= x && (m == n - 1 || v[m + 1] > x))
            return m + 1;
        if (v[m] <= x)
            i = m + 1;
        else
            j = m - 1;
    }
}

int type2(int x) {
    int i = 0, j = n - 1;
    while (i <= j) {
        int m = i + (j - i) / 2;
        if (v[m] >= x && (m == 0 || v[m - 1] < x))
            return m + 1;
        if (v[m] < x)
            i = m + 1;
        else
            j = m - 1;
    }
}

int main()
{
    fin = fopen("cautbin.in", "r");
    fout = fopen("cautbin.out", "w");

    fscanf(fin, "%i", &n);
    for (int i = 0;i < n;++i)
        fscanf(fin, "%i ", &v[i]);
    fscanf(fin, "%i", &m);
    while (m--) {
        int t, x;
        fscanf(fin, "%i %i", &t, &x);
        int res;
        if (t == 0) res = type0(x);
        else if (t == 1) res = type1(x);
        else res = type2(x);
        fprintf(fout,"%i\n", res);
    }

  
    return 0;
}