#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int N, A[100000], M, query, i, x;

int newSearch_upper(int val)
{
    int i, step;
    for (step = 1; step < N; step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < N && A[i + step] <= val)
           i += step;

    if (i>0)
        return i;
    else
        return -1;
}

int newSearch_lower(int val)
{
    int i, step;
    for (step = 1; step < N; step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < N && A[i + step] < val)
           i += step;
    return i+1;
}

int oldSearch_upper(int val)
{
    int ls, ld, mijl;
    ls=1; ld=N;
    while (ls<=ld)
    {
        mijl=(ls+ld)/2;
        if (val==A[mijl] && A[mijl+1]!=val)
            return mijl;
        else if (val>=A[mijl])
            ls=mijl+1;
        else
            ld=mijl-1;
    }
    return -1;
}

/*
int oldSearch_lower(int val)
{
    int ls, ld, mijl;
    ls=1; ld=N;
    while (ls<=ld)
    {
        mijl=(ls+ld)/2;
        if (val==A[mijl] && A[mijl-1]!=val)
            return mijl;
        else if (val<=A[mijl])
            ld=mijl-1;
        else
            ls=mijl+1;
    }
}
*/

int main()
{
    fin>>N;
    for (i=1;i<=N;i++)
        fin>>A[i];
    fin>>M;
    for (i=1;i<=M;i++)
    {
        fin>>query>>x;
        if (query==0) fout<<oldSearch_upper(x)<<"\n";
        else if (query==1) fout<<newSearch_upper(x)<<"\n";
        else fout<<newSearch_lower(x)<<"\n";
    }

return 0;
}