#include <fstream>

using namespace std;

int binarySearch(int type, int value, int a[], int N);

int main()
{
    int N, M, type, value, i;
    ifstream f("cautbin.in");
    f >> N;
    int a[N];
    for (i = 0; i < N; i++)
        f >> a[i];
    f >> M;

    ofstream g("cautbin.out");
    for (i = 0; i < M; i++)
    {
        f >> type >> value;
        g << binarySearch(type, value, a, N) << '\n';
    }
    f.close();
    g.close();

    return 0;
}

int binarySearch(int type, int value, int a[], int N)
{
    int pos = 0, step;
    step = (1 << 21);

    while (step >>= 1)
    {
        if (pos + step < N && a[pos + step] <= value)
            pos += step;
    }

    if (type == 0 && a[pos] != value)
        pos = -2;
    else if (type == 2)
    {
        if (a[pos] == value)
        {
            while (pos > 0 && a[pos - 1] == value)
                pos--;
        }
        else
        {
            if (pos != 0)
                pos++;
        }
    }

    return ++pos;
}