#include <fstream>

using namespace std;

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

int a[100001];

int CautareBinara0(int l, int r, int nr)
{
    int m;
    while(l <= r)
    {
        m = (l + r) / 2;
        if (a[m] <= nr)
            l = m + 1;
        else
            r = m - 1;
    }
    m = (l + r) / 2;

    if (a[m] > nr)
        m --;
    if (a[m] == nr)
        return m;
    return -1;
}
int CautareBinara1(int l, int r, int nr)
{
    int m;
    while(l < r)
    {
        m = (l + r) / 2;
        if (a[m] <= nr)
            l = m + 1;
        else
            r = m - 1;
    }
    m = (l + r) / 2;

    if (a[m] > nr)
        m--;
    return m;
}
int CautareBinara2(int l, int r, int nr)
{
    int m;
    while(l < r)
    {
        m = (l + r) / 2;
        if (a[m] < nr)
            l = m + 1;
        else
            r = m - 1;
    }
    m = (l + r) / 2;

    if (a[m] < nr)
        m++;
    return m;
}
int main()
{
    int n, m, tip, x;
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> a[i];
    fin >> m;
    while(m)
    {
        fin >> tip >> x;
        if(tip == 0)
            fout << CautareBinara0(1, n, x) << '\n';
        if(tip == 1)
            fout << CautareBinara1(1, n, x) << '\n';
        if(tip == 2)
            fout << CautareBinara2(1, n, x) << '\n';
        m--;

    }
    return 0;
}