#include <fstream>
#include <vector>
using namespace std;

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

int BS(int c, int x, vector<int> &v)
{
    int l = 0;
    int r = v.size() - 1;

    int ind1 = -1;
    int ind2 = -1;
    int ind3 = -1;

    while(l <= r)
    {
        int m = l + (r - l) / 2;

        if (v[m] == x)
        {
            ind1 = m;
            ind2 = m;
            ind3 = m;

            if (c == 0 || c == 1)
                l = m + 1;
            else
                r = m - 1;
        }
        else if (v[m] < x)
        {
            ind2 = m;
            l = m + 1;
        }
        else
        {
            ind3 = m;
            r = m - 1;
        }
    }

    if (c == 0) return ind1;
    else if (c == 1) return ind2;
    else return ind3;
}

int main()
{
    vector<int> v;
    v.reserve(100006);

    int n, m;
    fin >> n;
    for (int i = 0; i < n; i++)
    {
        int x;
        fin >> x;
        v.push_back(x);
    }

    fin >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, c;
        fin >> c >> x;
        fout << BS(c, x, v) + 1 << '\n';
    }

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