#include <fstream>

using namespace std;

ifstream F ("cautbin.in");
ofstream G ("cautbin.out");

int N, M, v[100002], c, x;
int bs0(int y)
{
    int st = 0, dr = N - 1, gasit = 0, mij;
    while (!gasit && st <= dr)
    {
        mij = (st + dr) / 2;
        if (v[mij] == y)
            gasit = 1;
        else
        {
            if (v[mij] < y)
                dr = mij - 1;
            else
                st = mij + 1;
        }
    }
    if (!gasit)
        return -1;
    while (v[mij] == y) ++ mij;
    return mij;
}

int bs1(int y)
{
    int st = 0, dr = N - 1, gasit = 0, mij;
    while (!gasit && st <= dr)
    {
        mij = (st + dr) / 2;
        if (v[mij] == y)
            gasit = 1;
        else
        {
            if (v[mij] < y)
                dr = mij - 1;
            else
                st = mij + 1;
        }
    }
    if (gasit)
    {
        while (v[mij] == y) ++ mij;
        return mij;
    }
    else
    {
        mij = (st + dr) / 2;
        while (v[mij] > y) -- mij;
        return mij;
    }
}

int bs2(int y)
{
    int st = 0, dr = N - 1, gasit = 0, mij;
    while (!gasit && st <= dr)
    {
        mij = (st + dr) / 2;
        if (v[mij] == y)
            gasit = 1;
        else
        {
            if (v[mij] < y)
                dr = mij - 1;
            else
                st = mij + 1;
        }
    }
    if (gasit)
    {
        while (v[mij] == y) -- mij;
        return mij + 2;
    }
    else
    {
        mij = (st + dr) / 2;
        while (v[mij] < y) ++ mij;
        return mij;
    }
}

int main()
{
    F >> N;
    for (int i = 0; i < N; ++ i)
        F >> v[i];
    F >> M;
    for (int i = 0; i < M; ++ i)
    {
        F >> c >> x;
        if (!c) G << bs0(x) << '\n';
        else if (c == 1) G << bs1(x) << '\n';
        else if (c == 2) G << bs2(x) << '\n';
    }
    return 0;
}