#include <iostream>
#include <fstream>

using namespace std;

int n, a[100001];

int CautareBinara(int numar, int tip)
{
    if(tip == 0 && (numar < a[1] || numar > a[n]))
        return -1;

    int stanga = 1, dreapta = n, mijloc;

    while(stanga <= dreapta)
    {
        mijloc = (stanga + dreapta) / 2;

        if(a[mijloc] <= numar)
            stanga = mijloc + 1;
        else
            dreapta = mijloc - 1;
    }
    if(tip == 0)
    {
        if(a[dreapta] == numar)
            return dreapta;
        return -1;
    }
    if(tip == 1)
        return dreapta;
    return stanga;
}

int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");

    f >> n;

    for(int i = 1; i <= n; i++)
        f >> a[i];

    int numar_intrebari, tip, numar;

    f >> numar_intrebari;

    for(int i = 1; i <= numar_intrebari; i++)
    {
        f >> tip >> numar;
        if(tip == 2)
            g << CautareBinara(numar - 1, tip) << '\n';
        else
            g << CautareBinara(numar, tip) << '\n';
    }

    return 0;
}