#include <iostream>
#include <fstream>

using namespace std;

const int M = 100001;

ifstream fcin("cautbin.in");
ofstream fcout("cautbin.out");

int n, x[M], t;

int search0(int d)
{
    int i = 1, j = n, poz = -1;
    while (i <= j)
    {
        int m = (i + j) / 2;
        if (x[m] < d)
            i = m + 1;
        if (x[m] > d)
            j = m - 1;
        if (x[m] == d)
        {
            poz = m;
            i = m + 1;
        }
    }
    return poz;
}

int search1(int d)
{
    int i = 1, j = n, poz = -1;
    while (i <= j)
    {
        int m = (i + j) / 2;
        if (x[m] < d)
            i = m + 1;
        if (x[m] > d)
            j = m - 1;
        if (x[m] <= d)
        {
            poz = m;
            i = m + 1;
        }
    }
    return poz;
}

int search2(int d)
{
    int i = 1, j = n, poz = -1;
    while (i <= j)
    {
        int m = (i + j) / 2;
        if (x[m] < d)
            i = m + 1;
        if (x[m] > d)
            j = m - 1;
        if (x[m] >= d)
        {
            poz = m;
            j = m - 1;
        }
    }
    return poz;
}

int main()
{
    int q, d;
    fcin >> n;
    for (int i = 1; i <= n; ++i)
        fcin >> x[i];
    fcin >> t;
    while (t)
    {
        fcin >> q >> d;
        if (q == 0)
            fcout << search0(d) << '\n';
        else
            if (q == 1)
                fcout << search1(d) << '\n';
            else
                fcout << search2(d) << '\n';
        --t;
    }
}