#include <iostream>
#include <fstream>

using namespace std;

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

long long A[500001], i, ok, n, x, st, dr, mij, z, m;

int main()
{
    f >> n;

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

    f >> m;

    for (i = 1; i <= m; i++)
    {

    f >> z >> x;

    st = 1;
    dr = n;

    if (z == 0)
    {
        while (st <= dr)
        {
            mij = (st + dr) / 2;
            if (x >= A[mij]) st = mij + 1;
                else dr = mij - 1;
        }

        if (A[st - 1] == x) g << st - 1 << '\n';
            else g << -1 << '\n';
    }
    else if (z == 1)
    {
        while (st <= dr)
        {
            mij = (st + dr) / 2;
            if (x >= A[mij]) st = mij + 1;
                else dr = mij - 1;
        }

        g << st - 1 << '\n';
    }
    else if (z == 2)
    {
        while (st <= dr)
        {
            mij = (st + dr) / 2;
            if (x <= A[mij]) dr = mij - 1;
                else st = mij + 1;
        }
        g << dr + 1 << '\n';
    }
    }

    return 0;
}