# include <fstream>
# define nmax 100005

using namespace std;

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

int n, m;
int a[nmax];

int first_binary(int low, int high, int key)
{
    int m;
    while(low < high) {
        m = low + (high - low)/2;
        if(a[m] > key)
            high = m - 1;
        else
            low = m + 1;
    }

    m = low + (high - low)/2;
    if(a[m] > key) -- m;
    if(a[m] == key) return m;
    else return -1;
}

int second_binary(int low, int high, int key)
{
    int m;
    while(low < high) {
        m = low + (high - low)/2;
        if(a[m] <= key)
            low = m + 1;
        else
            high = m;
    }

    m = low + (high - low)/2;
    if(a[m] > key) --m;
    return m;
}

int third_binary(int low, int high, int key)
{
    int m;
    while(low < high) {
        m = low + (high - low)/2;
        if(a[m] < key)
            low = m + 1;
        else
            high = m;
    }

    m = low + (high - low)/2;
    if(a[m] < key) ++ m;
    return m;
}

int main()
{
    int i, p, q;
    fin >> n;
    for(i = 1; i <= n; ++ i) fin >> a[i];
    fin >> m;
    i = 1;
    while(i <= m) {
        fin >> p >> q;
        if(!p) fout << first_binary(1, n, q);
        if(p == 1) fout << second_binary(1, n, q);
        else if(p == 2) fout << third_binary(1, n, q);
        ++ i;
        fout << "\n";
    }
    return 0;
}