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

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

int v[100002], a, ok, x, n, b, y;

int cb0(int N )
{
    int s=1, d=N, m;
    while ( s <= d )
    {
        m = (s + d) / 2;
        if (ok == 0)
        {
            if (v[m] == x)
            {
                while ( x == v[m] )
                    m ++ ;
                return m-1 ;
            }
            if (v[m] < x)
                s = m + 1;
            if (v[m] > x)
                d = m - 1;
        }
    }
    return -1;
}

int cb1(int N )
{
    int s=1, d=N, sol, m=(s+d)/2;
    while ( s <= d )
    {
        if ( v[m] <= x ) {
            s = m + 1;
            sol = m;
        }
        if ( v[m] > x )
            d = m - 1;
        m = (s + d) / 2;
    }
    return sol ;
}
int cb2(int N )
{
    int s=1, d=N, sol, m=(s+d)/2;
    while ( s <= d )
    {
        if ( v[m] >= x ) {
            d = m - 1;
            sol = m;
        }
        if ( v[m] < x )
            s = m + 1;
        m = (s + d) / 2;
    }
    return sol ;
}
int main()
{
    cin >> n ;
    for ( int i = 1 ; i <= n ; i ++ )
    {
        cin >> v[i] ;
    }
    cin >> b ;
    for ( int i = 1 ; i <= b ; i ++ )
    {
        cin >> ok >> x ;
        if ( ok == 0 )
            cout << cb0(n) ;
        if ( ok == 1 )
            cout << cb1(n) ;
        if ( ok == 2 )
            cout << cb2(n) ;
        cout << '\n' ;
    }
    return 0;
}