#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

/*-------- Data --------*/
vector<int>v;
int nrIntrebari, ceFac, lungimeVector, ceCaut;
/*-------- --------*/

inline int mid(int a, int b) {
    return a + (b - a)/2;
}

int citescVector() {
    //Functie ce citeste vectorul
    in >> lungimeVector;
    while (lungimeVector) {
        int value;
        in >> value;
        v.push_back(value);
        lungimeVector--;
    }
    return v.size() - 1;
}

int ceaMaiMarePozX() {
    //Caut cea mai mare pozitie in care apare x

    int stanga = 0;
    int dreapta = lungimeVector;
    int pozitie = -1;
    int mijloc;

    while (stanga <= dreapta) {
        mijloc = mid(stanga, dreapta);
        if (v[mijloc] == ceCaut) {
            pozitie = mijloc;
            stanga = mijloc + 1;
        } else if (v[mijloc] < ceCaut) {
            stanga = mijloc + 1;
        } else if (v[mijloc] > ceCaut) {
            dreapta = mijloc - 1;
        }
    }

    if (pozitie == -1)
        return -1;
    return pozitie + 1;
}

int infimum() {
    //Infimum ca la mate

    int stanga = 0;
    int dreapta = lungimeVector;
    int pozitie;
    int mijloc;

    while (stanga <= dreapta) {
        mijloc = mid(stanga, dreapta);
        if (v[mijloc] <= ceCaut) {
            pozitie = mijloc;
            stanga = mijloc + 1;
        } else if (v[mijloc] > ceCaut) {
            dreapta = mijloc - 1;
        }
    }

    return pozitie + 1;
}

int supremum() {
    //Supremum ca la mate

    int stanga = 0;
    int dreapta = lungimeVector;
    int pozitie;
    int mijloc;

    while (stanga <= dreapta) {
        mijloc = mid(stanga, dreapta);
        if (v[mijloc] >= ceCaut) {
            pozitie = mijloc;
            dreapta = mijloc - 1;
        } else if (v[mijloc] < ceCaut) {
            stanga = mijloc + 1;
        }
    }

    return pozitie + 1;
}

int main() {

    int afisez;
    lungimeVector = citescVector();
    in >> nrIntrebari;

    while (nrIntrebari--) {
        in >> ceFac >> ceCaut;
        if (ceFac == 0) {
            afisez = ceaMaiMarePozX();
            out << afisez;
        } else if (ceFac == 1) {
            afisez = infimum();
            out << afisez;
        } else {
            afisez = supremum();
            out << afisez;
        }

    out << "\n";
    }

    return 0;
}