#include <fstream>

using namespace std;

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

#define N 100001

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

int cb0(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 v[m]==key ? m:-1;
}

int cb1(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;

    return v[m]==key ? m:m-1;
}

int cb2(int key)
{
    int st = 1, dr = n, m;

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

    return v[m]==key ? m:m-1;
}

void citire()
{
    in >> n;

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

    in >> T;

    while(T--)
    {
        in >> tip >> x;

        switch(tip)
        {
            case 0 : {out << cb0(x) << "\n";break;}
            case 1 : {out << cb1(x) << "\n";break;}
            case 2 : {out << cb2(x) << "\n";break;}
        }
    }
}

int main()
{
    citire();

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