#include <bits/stdc++.h>

using namespace std;

ifstream fin ("cautbin.in");
ofstream fout("cautbin.out");

int n, m, st, dr, mij, poz, x, cerinta;
int v[100010];

void cautare0(int x) {
    poz = -1;
    st = 1, dr = n;
    while(st <= dr) {
        mij =(st + dr)/2;
        if(v[mij] == x) {
            poz = mij;
        }
        if(v[mij] <= x) {
            st = mij + 1;
        }else dr = mij - 1;
    }
}

void cautare1(int x) {
    poz = -1;
    st = 1, dr = n;
    while(st <= dr) {
        mij =(st + dr)/2;
        if(v[mij] <= x) {
            st = mij + 1;
            poz = mij;
        }else dr = mij - 1;
    }
}

void cautare2(int x) {
    poz = -1;
    st = 1, dr = n;
    while(st <= dr) {
        mij =(st + dr)/2;
        if(v[mij] >= x) {
            dr = mij - 1;
            poz = mij;
        }else st = mij + 1;
    }
}

int main() {
    fin >> n;
    for(int i = 1; i <= n; i++) {
        fin >> v[i];
    }
    fin >> m;
    for(int i = 1; i <= m; i++) {
        fin >> cerinta >> x;
        if(cerinta == 0)cautare0(x);
        else if(cerinta == 1)cautare1(x);
        else if(cerinta == 2)cautare2(x);
        fout << poz << '\n';
    }
    return 0;
}