#include <fstream>

using namespace std;

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

#define N 100000

int v[N], n, t, key, type;

int bin0();
int bin1();
int bin2();

int main()
{
    in >> n;

    for(int i=0;i<n;i++)
        in >> v[i];

    in >> t;

    for(int i=1;i<=t;i++)
    {
        in >> type >> key;

        if(!type)
            out << bin0() << "\n";
        else if(type==1)
            out << bin1() << "\n";
        else
            out << bin2() << "\n";
    }

    in.close();
    out.close();
    return 0;
}

int bin0()
{
    int st=0, dr=n-1, m;

    while(st<dr)
    {
        m=(st+dr)/2;
        if(v[m]<=key)
            st=m+1;
        else
            dr=m;
    }
    m=(st+dr)/2;

    if(v[m]>key)
        m--;

    if(v[m]!=key)
        return -1;

    return m+1;
}

int bin1()
{
    int st=0, dr=n-1, m;

    while(st<dr)
    {
        m=(st+dr)/2;
        if(v[m]>key)
            dr=m-1;
        else
            st=m+1;
    }
    m=(st+dr)/2;

    if(v[m]>key)
        m--;

    return m+1;
}

int bin2()
{
    int st=0, dr=n-1, m;

    while(st<dr)
    {
        m=(st+dr)/2;
        if(v[m]<key)
            st=m+1;
        else
            dr=m;
    }
    m=(st+dr)/2;

    return m+1;
}