#include <fstream>

#define NMAX 100010

using namespace std;

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

int n;
unsigned int v[NMAX], rez;

int cautUltAp(int index, int shift, unsigned int item)
{
    if (v[index] <= item)
    {
        if (index < n - 1)
        {
            if (v[index + 1] > v[index])
                rez =  index;

        }
        else
            rez = index;
    }

    while (n - index - 1 < shift && shift)
        shift >>= 1;


    while (shift && v[index + shift] > item)
    {
            shift >>= 1;
    }

    if (shift)
        cautUltAp(index + shift, shift, item);
}

int cautPrimAp(int index, int shift, unsigned int item)
{
    if (v[index] >= item)
    {
        if (index > 0)
        {
            if (v[index] > v[index - 1])
                rez =  index;

        }
        else
            rez = index;
    }

    while (index < shift && shift)
        shift >>= 1;


    while (shift && v[index - shift] < item)
    {
            shift >>= 1;
    }

    if (shift)
        cautPrimAp(index - shift, shift, item);
}

int cautBin()
{
    int t, nfals;
    unsigned int item;
    f >> t >> item;

    int shift = 1;
    nfals = n;

    while (nfals)
    {
        shift <<= 1;
        nfals >>= 1;
    }
    shift >>= 1;

    switch (t)
    {
    case 0:
        {
            cautUltAp(0, shift, item);
            if (v[rez] == item)
                return rez + 1;
            else
                return -1;
        } break;
    case 1:
        {
            cautUltAp(0, shift, item);
            return rez + 1;
        } break;
    case 2:
        {
            cautPrimAp(n - 1, shift, item);
            return rez + 1;
        } break;
    default:
        { } break;
    }
}

int main()
{
    f >> n;
    for (int i = 0; i < n; i++)
    {
        f >> v[i];
    }

    int m;
    f >> m;
    for (int i = 0; i < m; i++)
        g << cautBin() << "\n";

    return 0;
}