#include <fstream>

using namespace std;

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

int n, m, k, a;
int v[100001];

int cautbin0(int x)
{
    int l = 0, r = n + 1;
    while (r - l > 1)
    {
        int mij = (l + r) / 2;
        if(v[mij] > x)
            r = mij;
        else
            l = mij;
    }
    if (l == 0 || v[l] != x)
        return -1;
    return l;
}

int cautbin1(int x)
{
    int l = 0, r = n + 1;
    while (r - l > 1)
    {
        int mij = (l + r) / 2;
        if (v[mij] > x)
            r = mij;
        else
            l = mij;
    }
    return l;
}

int cautbin2(int x)
{
    int l = 0, r = n + 1;
    while (r - l > 1)
    {
        int mij = (l + r) / 2;
        if (v[mij] < x)
            l = mij;
        else
            r = mij;
    }
    return r;
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    fin >> m;

    for (int i = 1; i <= m; ++i)
    {
        fin >> k >> a;
        if (k == 0)
            fout << cautbin0(a) << "\n";
        else if (k == 1)
            fout << cautbin1(a) << "\n";
        else if (k == 2)
            fout << cautbin2(a) << "\n";
    }

    fin.close();
    fout.close();
    return 0;
}