#include <fstream>

using namespace std;

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

#define N 100001

int v[N], n, k, x, tip;

int caut0(int key);
int caut1(int key);
int caut2(int key);

int main()
{
    in >> n;

    for(int i=1;i<=n;i++)
        in >> v[i];
    in >> k;
    for(int i=1;i<=k;i++)
    {
        in >> tip >> x;
        if(tip==0)
            out << caut0(x) << "\n";
        else if(tip==1)
            out << caut1(x) << "\n";
        else if(tip==2)
            out << caut2(x) << "\n";
    }

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

int caut0(int key)
{
    int st=1, dr=n, 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--;
    if(v[m]!=key)
        return -1;
    return m;
}

int caut1(int key)
{
    int st=1, dr=n, 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;
}

int caut2(int key)
{
    int st=1, dr=n, 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--;
    return m;
}