#include <iostream>
#include <fstream>

using namespace std;
ifstream fin ("cautbin.in");
ofstream fout("cautbin.out");

int n, m, v[ 100005 ], c, x, i;

int caut_bin0()
{
    int p = 1, u = n, m;
    while ( p < u )
    {
        m = ( p + u ) / 2;
        if ( v[ m ] <= x )
        {
            p = m + 1;
        }
        else
        {
            u = m;
        }
    }
    m = p;
    if ( v[ m ] > x )
    {
        m--;
    }
    if ( v[ m ] == x )
    {
        return m;
    }
    return -1;
}

int caut_bin1()
{
    int p = 1, u = n, m;
    while ( p < u )
    {
        m = ( p + u ) / 2;
        if ( v[ m ] <= x )
        {
            p = m + 1;
        }
        else
        {
            u = m;
        }
    }
    m = p;
    if ( v[ m ] > x )
    {
        m --;
    }
    return m;
}

int caut_bin2()
{
    int p = 1, u = n, m;
    while ( p < u )
    {
        m = ( p + u ) / 2;
        if ( v[ m ] >= x )
        {
            u = m;
        }
        else
        {
            p = m + 1;
        }
    }
    m = p;
    if ( v[ m ] < x )
    {
        m++;
    }
    return m;
}

int main()
{
    fin>>n;
    for ( i = 1; i <= n; i++ )
    {
        fin>>v[ i ];
    }
    fin>>m;
    while( m-- )
    {
        fin>>c>>x;
        if ( c == 0 )
        {
            fout<<caut_bin0()<<'\n';
        }
        else if ( c == 1)
        {
            fout<<caut_bin1()<<'\n';
        }
        else if ( c == 2 )
        {
            fout<<caut_bin2()<<'\n';
        }
    }
    return 0;
}