#include <iostream>
#include <fstream>

using namespace std;

const int M = 100001;

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

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

int search0()
{
    int poz = -1, p = 0, u = n - 1;
    while (p <= u)
    {
        int m = (p + u) / 2;
        if (x[m] == d)
            poz = m;
        if (x[m] <= d)
            p = m + 1;
        else
            u = m - 1;
    }
    return poz + 1;
}

int search1()
{
    int poz = -1, p = 0, u = n - 1;
    while (p <= u)
    {
        int m = (p + u) / 2;
        if (x[m] <= d)
        {
            poz = m;
            p = m + 1;
        }
        else
            u = m - 1;
    }
    return poz + 1;
}

int search2()
{
    int poz = -1, p = 0, u = n - 1;
    while (p <= u)
    {
        int m = (p + u) / 2;
        if (x[m] >= d)
        {
            poz = m;
            u = m - 1;
        }
        else
            p = 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;
    }
}