#include <fstream>
#include <vector>
using namespace std;

ifstream is("bs.in");
ofstream os("bs.out");

vector<int> a;
int n, m, x, y;

int BS0(int y);
int BS1(int y);
int BS2(int y);

int main()
{
    is >> n;
    a.resize(n+1);
    for ( int i = 1; i <= n; i++ )
        is >> a[i];
    is >> m;
    for ( int i = 1; i <= m; i++ )
    {
        is >> x >> y;
        if ( x == 0 )
            os << BS0(y) << '\n';
        if ( x == 1 )
            os << BS1(y) << '\n';
        if ( x == 2 )
            os << BS2(y) << '\n';
    }
    is.close();
    os.close();
    return 0;
}

int BS0(int y)
{
    int st, dr, mij;
    st = 1;
    dr = n;
    while ( st < dr )
    {
        mij = ( st + dr ) / 2;
        if ( a[mij] <= y )
            st = mij + 1;
        else
            dr = mij;
    }
    mij = ( st + dr ) / 2;
    if ( a[mij] > y ) mij--;
    if ( a[mij] == y ) return mij;
    return -1;
}
int BS1(int y)
{
    int st, dr, mij;
    st = 1;
    dr = n;
    while ( st < dr )
    {
        mij = ( st + dr ) / 2;
        if ( a[mij] <= y )
            st = mij + 1;
        else
            dr = mij;
    }
    mij = ( st + dr ) / 2;
    if (a[mij] > y)
       --mij;
    return mij;
}
int BS2(int y)
{
    int st, dr, mij;
    st = 1;
    dr = n;
    while ( st < dr )
    {
        mij = ( st + dr ) / 2;
        if ( a[mij] < y )
            st = mij + 1;
        else
            dr = mij;
    }
    mij = ( st + dr ) / 2;
    if (a[mij] < y)
       ++mij;
    return mij;
}