#include <bits/stdc++.h>

using namespace std;

const int NMAX = 100100;

int numere[NMAX];
int n, m, x;

void citire() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &numere[i]);
    }
}

int tip0iterativ() {
    int st = 1, dr = n;
    int mid, last = dr + 1;
    while(st <= dr) {
        mid = (st + dr) / 2;
        if(numere[mid] <= x) {
            st = mid + 1;
            last = mid;
        } else dr = mid - 1;
    }

    if(numere[last] == x)
        return last;
    else return -1;
}

int tip1iterativ() {
    int st = 1, dr = n;
    int mid, last = dr + 1;
    while(st <= dr) {
        mid = (st + dr) / 2;
        if(numere[mid] <= x) {
            st = mid + 1;
            last = mid;
        } else if (numere[mid] > x) {
            dr = mid - 1;
        }
    }

    if(numere[last] <= x)
        return last;

}

int tip2iterativ() {
    int st = 1, dr = n;
    int mid, last = dr + 1;
    while(st <= dr) {
        mid = (st + dr) / 2;
        if(numere[mid] < x) {
            st = mid + 1;
        } else {
                last = mid;
            dr = mid - 1;
        }
    }

    if(numere[last] >= x)
        return last;
}

void rezolvare() {
    scanf("%d", &m);
    int tip;
    for(int i = 1; i <= m; i++) {
        scanf("%d%d", &tip, &x);
        if(tip == 0)
            printf("%d\n", tip0iterativ());
        if(tip == 1)
            printf("%d\n", tip1iterativ());
        if(tip == 2)
            printf("%d\n", tip2iterativ());
    }
}



int main() {

    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

    citire();
    rezolvare();

    return 0;
}