#include <iostream>
#include <fstream>

using namespace std;

int cautare_binara0(int v[100001], int stg, int dr, int valoare)
{
    int mijl;

    mijl = (stg + dr) / 2;

    if(stg < dr)
    {
        if(v[mijl] < valoare)
            return cautare_binara0(v, mijl + 1, dr, valoare);
        else if(v[mijl] > valoare)
            return cautare_binara0(v, stg, mijl - 1, valoare);
    }

    while(v[mijl + 1] == valoare)
        mijl++;

    if(v[mijl] == valoare)
        return mijl;

    return -1;
}

int cautare_binara1(int v[100001], int stg, int dr, int valoare)
{
    int mijl;

    mijl = (stg + dr) / 2;

    if(stg < dr)
    {
        if(v[mijl] < valoare)
            return cautare_binara1(v, mijl + 1, dr, valoare);
        else if(v[mijl] > valoare)
            return cautare_binara1(v, stg, mijl - 1, valoare);
    }

    while(v[mijl + 1] <= valoare)
        mijl++;

    return mijl;
}

int cautare_binara2(int v[100001], int stg, int dr, int valoare)
{
    int mijl;

    mijl = (stg + dr) / 2;

    if(stg < dr)
    {
        if(v[mijl] <= valoare)
            return cautare_binara2(v, mijl + 1, dr, valoare);
        else if(v[mijl] > valoare)
            return cautare_binara2(v, stg, mijl - 1, valoare);
    }

    while(v[mijl - 1] >= valoare)
        mijl--;

    return mijl;
}

int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    int v[100001], n, i, m, tip, x;

    f >> n;

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

    f >> m;

    for(i=1; i<=m; i++)
    {
        f >> tip >> x;

        if(tip == 0)
            g << cautare_binara0(v, 1, n, x) << endl;
        else if(tip == 1)
            g << cautare_binara1(v, 1, n, x) << endl;
        else if(tip == 2)
            g << cautare_binara2(v, 1, n, x) << endl;
    }

    f.close();
    g.close();
    return 0;
}