#include <fstream>

using namespace std;

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

int v[100002], n;

int caut_bin0(int s, int d, int nr)
{
    int poz = -1, mij;

    while(s <= d)
    {
        mij = s + (d - s)/2;

        if(v[mij] == nr)
        {
            poz = mij;

            while(v[poz] == v[poz + 1])
                poz++;

            return poz;
        }
        else
            if(nr < v[mij])
                d = mij - 1;
            else
                s = mij + 1;
    }

    return -1;
}

int caut_bin1(int s, int d, int nr)
{
    int poz = -1, mij;

    while(s <= d)
    {
        mij = s + (d - s)/2;

        if(v[mij] == nr)
        {
            poz = mij;

            while(v[poz] == v[poz + 1])
                poz++;

            return poz;
        }
        else
            if(nr < v[mij])
                d = mij - 1;
            else
                s = mij + 1;
    }

    return d;
}

int caut_bin2(int s, int d, int nr)
{
    int poz = -1, mij;

    while(s <= d)
    {
        mij = s + (d - s)/2;

        if(v[mij] == nr)
        {
            poz = mij;

            while(v[poz] == v[poz - 1])
                poz--;

            return poz;
        }
        else
            if(nr < v[mij])
                d = mij - 1;
            else
                s = mij + 1;
    }

    return s;
}

int main()
{

    int m, intreb, i, x;

    f >> n;

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

    f >> m;

    for(i = 0; i < m; i++)
    {
        f >> intreb >> x;

        if(intreb == 0)
            g << caut_bin0(1, n, x) << '\n';
        else
            if(intreb == 1)
                g << caut_bin1(1, n, x) << '\n';
            else
                g << caut_bin2(1, n, x) << '\n';
    }

    return 0;
}