#include <iostream>
#include <fstream>

using namespace std;

const int M = 100001;

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

int n, x[M], t, q, d;

int search0()
{
    int i = 0, j = n - 1, 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 + 1;
}

int search1()
{
    int i = 0, j = n - 1, 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 + 1;
}

int search2()
{
    int i = 0, j = n - 1, 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 + 1;
}

int main()
{
    fcin >> n;
    for (int i = 0; i < n; ++i)
        fcin >> x[i];
    fcin >> t;
    while (t)
    {
        fcin >> q >> d;
        switch (q)
        {
            case 0:
                fcout << search0() << '\n';
                break;
            case 1:
                fcout << search1() << '\n';
                break;
            case 2:
                fcout << search2() << '\n';
                break;
        }
        --t;
    }
}