#include <iostream>
#include <cstdio>
using namespace std;
int n;
int *v;

int cautbin(int x) {
    int lf = 0, rf = n-1;
    while(lf < rf - 1) {
        int mid = lf + (rf-lf)/2;
        if(v[mid] <= x) {
            lf = mid;
        }
        else rf = mid-1;
    }
    if(v[lf+1] == x) return lf+1;
    return lf;
}

int cautbin3(int x) {
    int lf = 0, rf = n-1;
    while(lf < rf - 1) {
        int mid = lf + (rf-lf)/2;
        if(v[mid] >= x) {
            rf = mid;
        }
        else lf = mid+1;
    }
    if(v[lf] == x) return lf;
    return lf+1;
}

int main() {
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out" , "w", stdout);
    scanf("%d", &n);
    v = new int[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
    }
    int m;
    scanf("%d", &m);
    for(int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        if(x == 0) {
            int p = cautbin(y);
            printf("%d\n", v[p] == y ? p+1 : -1);
        }
        else if(x == 1) {
            int p = cautbin(y);
            printf("%d\n", p+1);
        }
        else {
            printf("%d\n", cautbin3(y)+1);
        }
    }
    delete[] v;
    return 0;
}