#include <fstream>
using namespace std;
 
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
 
 
int N, M;
int A[100005];
 
int BS2(int x); // OK.. cea mai mica pozitie pe care se afla un nr <= cu X
 
int BS1(int x);// OK.. cea mai mare
 
int BS0(int x);// OK.. ce mai mare pozitie pe care se afla X
 
 
int main()
{
    fin >> N;
    for ( int i = 1; i <= N; ++i )
        fin >> A[i];
    fin >> M;
    int op, X;
    while ( fin >> op >> X )
    {
        if ( !op )
            fout << BS0(X) << '\n';
        if ( op == 1 )
            fout << BS1(X) << '\n';
        if ( op == 2 )
            fout << BS2(X) << '\n';
    }
 
    fin.close();
    fout.close();
    return 0;
};
 
 
 
 
int BS2(int x)
{
    int hi = N + 1, lo = 0;
    while ( hi - lo > 1)
    {
        int med = (hi + lo) / 2;
 
        if ( x < A[med] )
            hi = med;
        else
            lo = med;
    }
 
    if ( A[lo] == x )
    {
        while ( A[lo] == x )
        {
            lo--;
        }
        return lo + 1;
    }
 
    return hi;
}
 
int BS1(int x)
{
    int hi = N + 1, lo = 0;
    while ( hi - lo > 1)
    {
        int med = (hi + lo) / 2;
 
        if ( x > A[med] )
            lo = med;
        else
            hi = med;
    }
 
    if ( A[hi] == x )
    {
        while ( A[hi] == x )
        {
            hi++;
        }
        return hi - 1;
    }
 
    return lo;
}
 
 
int BS0(int x)
{
    int hi = N + 1, lo = 0;
    while ( hi - lo > 1)
    {
        int med = (hi + lo) / 2;
 
        if ( x < A[med] )
            hi = med;
        else
            lo = med;
    }
 
    if ( A[lo] != x)
        return -1;
    else
        return lo;
}