#include <fstream>
using namespace std;

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

int n,a[100001],m,aux1,aux2;

void Read();
int BinarySearch(int x,int q);

int main()
{
    Read();
    for ( int i = 1; i <= m; i++ )
    {
        is >> aux1 >> aux2;
        os << BinarySearch(aux2,aux1) << '\n';

    }
    return 0;
}

void Read()
{
    is >> n;
    for ( int i = 1; i <= n; ++i )
    is >> a[i];
    is >> m;
}

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

    if ( q == 2)
    {
        while (p < u)
        {
            m = (p + u) / 2;
            if (a[m] < x)
            p = m + 1;
            else
            u = m;
        }
    m = (p + u) / 2;
    if (a[m] < x)
        m++;
    return m;
    }

}