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

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;
}