#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, v[100001], c, x, m;

int cautbin0(int x)
{
    int st = 1, dr = n;
    while(st <= dr)
    {
        int m = (st + dr) / 2;
        if(v[m] <= x)
            st = m + 1;
        else
            dr = m - 1;
    }
    m = (st + dr) / 2;

    while(v[m] > x)m--;
    if(v[m] == x)
        return m;
    return -1;
}

int cautbin1(int x)
{
    int st = 1, dr = n;
    while(st <= dr)
    {
        int m = (st + dr) / 2;
        if(v[m] <= x)
            st = m + 1;
        else
            dr = m - 1;
    }
    m = (st + dr) / 2;

    while(v[m] > x)m--;

    return m;
}

int cautbin2(int x)
{
    int st = 1, dr = n;
    while(st < dr)
    {
        int m = (st + dr) / 2;
        if(v[m] < x)
            st = m + 1;
        else
            dr = m;
    }
    m = (st + dr) / 2;

    while(v[m] < x)m++;

    return m;
}


int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
    {
        fin >> v[i];
    }
    fin >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> c >> x;
        if(c == 0)fout << cautbin0(x) << '\n';
        if(c == 1)fout << cautbin1(x) << '\n';
        if(c == 2)fout << cautbin2(x) << '\n';
    }
    return 0;
}