#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");

int n, m, a[100002];

int op0(int x, int st, int dr)
{
    if (st > dr) return -1;

    int mijl = (st+dr) / 2;
    if (a[mijl] <= x) return mijl;
    if (a[mijl] > x) return op0(x, st, mijl - 1);
    if (a[mijl] < x) return op0(x, mijl + 1, dr);
}
void op1(int x, int st, int dr, int &afis)
{
    if (st > dr) return;

    int mijl =(st+dr) / 2;
    if (a[mijl] > x) op1(x, st, mijl - 1, afis);
    else
    {
        if(afis < mijl)
            afis = mijl;
        op1(x, mijl + 1, dr, afis);

    }
}
void op2(int x, int st, int dr, int &afis)
{
    if (st > dr) return;

    int mijl = (st+dr) / 2;
    if (a[mijl] < x) op2(x, mijl + 1, dr, afis);
    else
    {
        if (afis > mijl) afis = mijl;
        op2(x, st, mijl - 1, afis);
    }
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> a[i];
    fin >> m;
    for (int i = 0; i < m; i++)
    {
        int c, x;
        fin >> c >> x;
        int poz = op0(x, 1, n);

        if (c == 0)
        {
            if (poz == -1)
            {
                fout << -1;
                continue;
            }
            int poz_copy = poz;
            while (a[poz_copy] == x)
                poz_copy++;
            fout << poz_copy - 1 << "\n";
        }
        if (c == 1)
        {
            int afis = -1;
            op1(x, 1, n, afis);
            fout << afis << "\n";
        }
        if (c == 2)
        {
            int afis = INT_MAX;
            op2(x, 1, n, afis);
            fout << afis << "\n";
        }
    }
    return 0;
}