#include <cstdio>
using namespace std;
const int NMAX = 100005;
int v[NMAX];
int n;
void cb(int op, int x)
{
    int st, dr, mij;
    st = 1;
    dr = n;
    while(st < dr) {
        if(op == 0) {
            mij = (st + dr + 1) / 2;
            if(v[mij] <= x) {
                st = mij;
            }
            else {
                dr = mij - 1;
            }
        }
        else if(op == 1) {
            mij = (st + dr + 1) / 2;
            if(v[mij] > x) {
                dr = mij - 1;
            }
            else {
                st = mij;
            }
        }
        else if(op == 2) {
            mij = (st + dr) / 2;
            if(v[mij] < x) {
                st = mij + 1;
            }
            else {
                dr = mij;
            }
        }
    }
    if(op == 0) {
        if(v[dr] == x) {
            printf("%d", dr);
        }
        else {
            printf("-1");
        }
    }
    else if(op == 1) {
        printf("%d", dr);
    }
    else if(op == 2) {
        printf("%d", dr);
    }
    printf("\n");
}

int main()
{
    int i, m, op, x;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d", &n);
    for(i = 1;i <= n; ++i) {
        scanf("%d", &v[i]);
    }
    scanf("%d", &m);
    for(i = 1;i <= m; ++i) {
        scanf("%d%d", &op, &x);
        cb(op, x);
    }
    return 0;
}