#include <fstream>

using namespace std;

const int N = 100000;

int main()
{
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");

    int n;
    in >> n;
    int v[N];
    for (int i = 0; i < n; i ++)
    {
        in >> v[i];
    }

    int m;
    in >> m;
    for (int k = 0; k < m; k ++)
    {
        int q, x;
        in >> q >> x;
        if (q == 0)
        {
            int st = 0, dr = n - 1, rez = -1;
            while (st <= dr)
            {
                int m = (st + dr) / 2;
                if (v[m] == x)
                {
                    rez = m;
                    st = m + 1;
                }
                else
                {
                    dr = m - 1;
                }
            }
            out << rez + 1 << '\n';
        }
        else if (q == 1)
        {
            int st = 0, dr = n - 1, rez = -1;
            while (st <= dr)
            {
                int m = (st + dr) / 2;
                if (v[m] <= x)
                {
                    rez = m;
                    st = m + 1;
                }
                else
                {
                    dr = m - 1;
                }
            }
            out << rez + 1 << '\n';
        }
        else
        {
            int st = 0, dr = n - 1, rez = -1;
            while (st <= dr)
            {
                int m = (st + dr) / 2;
                if (v[m] >= x)
                {
                    rez = m;
                    dr = m - 1;
                }
                else
                {
                    st = m + 1;
                }
            }
            out << rez + 1 << '\n';
        }
    }

    in.close();
    out.close();

    return 0;
}