#include <fstream>
using namespace std;
const int DIM = 100005;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
long n, nr[DIM], i, m;
void Binary_Search1(int x);
void Binary_Search2(int x);
void Binary_Search3(int x);
int main()
{
    long tip, val;
    fin >> n;
    for ( i = 1; i <= n; i++ )
        fin >> nr[i];
    fin >> m;
    for ( i = 1; i <= m; i++ )
    {
        fin >> tip >> val;
        if ( tip == 0 )
            Binary_Search1(val);
        if ( tip == 1 )
            Binary_Search2(val);
        if ( tip == 2 )
            Binary_Search3(val);
    }
    return 0;
}

void Binary_Search1(int x)
{
    long l = 1, r = n, mid, p = -1;
    while ( l <= r )
    {
        mid = ( l + r ) / 2;
        if ( nr[mid] > x )
            r = mid - 1;
        else
            l = mid + 1;
        if ( nr[mid] == x )
            p = mid;
    }
    fout << p << '\n';
}

void Binary_Search2(int x)
{
    long l = 1, r = n, mid, p;
    while ( l <= r )
    {
        mid = ( l + r ) / 2;
        if ( nr[mid] > x )
            r = mid - 1;
        else
            l = mid + 1;
        if ( nr[mid] <= x )
            p = mid;
    }
    fout << p << '\n';
}
void Binary_Search3(int x)
{
    long l = 1, r = n, mid, p;
    while ( l <= r )
    {
        mid = ( l + r ) / 2;
        if ( nr[mid] < x )
            l = mid + 1;
        else
            r = mid - 1;
        if ( nr[mid] >= x )
            p = mid;
    }
    fout << p << '\n';
}