#include <fstream>
#define N 100010

int v[N];

using namespace std;

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

int cautareBinara1(int inceput, int sfarsit, int cheie) 
{
    int mijloc;
    
    while(inceput <= sfarsit) {
        mijloc = (inceput + sfarsit) / 2;
        if(v[mijloc] <= cheie) {
            inceput = mijloc + 1;
        } else {
            sfarsit = mijloc - 1;
        }
    }
    mijloc = (inceput + sfarsit) / 2;
    if (v[mijloc] > cheie) {
        mijloc --;
    }
        
    if (v[mijloc] == cheie) {
        return mijloc;
    } 
    
    return -1;
}

int cautareBinara2(int inceput, int sfarsit, int cheie) 
{
    int mijloc;
    
    while (inceput < sfarsit) {
        mijloc = (inceput + sfarsit) / 2;
        if (v[mijloc] <= cheie) {
            inceput = mijloc + 1;
        } else {
            sfarsit = mijloc;
        }
    }
    mijloc = (inceput + sfarsit) / 2;
    if (v[mijloc] > cheie) 
        -- mijloc;
    return mijloc;
}

int cautareBinara3(int inceput, int sfarsit, int cheie) 
{
    int mijloc;
    
    while (inceput < sfarsit) {
        mijloc = (inceput + sfarsit) / 2;
        if (v[mijloc] < cheie) {
            inceput = mijloc + 1;
        } else {
            sfarsit = mijloc;
        }
    }
    mijloc = (inceput + sfarsit) / 2;
    if (v[mijloc] < cheie) 
        ++ mijloc;
    return mijloc;
}

int main()
{
    int n, tip, valoare;
    
    in >> n;
    
    for (int i=1;i<=n;i++) {
        in >> v[i];
    }
    
    int nrIntrebari;
    
    in >> nrIntrebari;
    
    while(nrIntrebari) {
        in >> tip >> valoare;
        
        if (tip == 0) {
            out << cautareBinara1(1, n , valoare) << "\n";
        } else if (tip == 1) {
            out << cautareBinara2(1, n, valoare) << "\n";
        } else {
            out << cautareBinara3(1, n, valoare) << "\n";
        }
        nrIntrebari --;
    }
    
    return 0;
}