#include <fstream>
#define NMAX 100001

using namespace std;

ofstream fout("cautbin.out");

int N, M, v[NMAX];

void CautareBinara( int cerinta, int x, int cap, int coada )
{
    int poz = -1;
    int mijloc = ( cap + coada ) / 2;
    switch(cerinta)
    {
    case 1:
        if ( v[mijloc] <= x )
            for ( int i = mijloc ; i <= N ; ++i )
            {
                if (v[i] <= x)
                    poz = i;
                else
                    break;
            }
        else
            if ( v[mijloc] > x )
                CautareBinara( cerinta, x, 1, mijloc - 1);
        break;

    case 2:
        if ( v[mijloc] >= x )
            for ( int i = mijloc ; i >= 1 ; --i )
            {
                if ( v[i] >= x)
                    poz = i;
                else
                    break;
            }
        else
            if ( v[mijloc] < x)
                CautareBinara( cerinta, x, mijloc + 1, N);
        break;

    default:
        if ( v[mijloc] == x )
            for ( int i = mijloc ; i <= N ; ++i )
            {
                if ( v[i] == x )
                    poz = i;
                else
                    break;
            }
        else
        {
            if (v[mijloc] < x)
                if (mijloc + 1 != N)
                    CautareBinara( cerinta, x, mijloc + 1, N );
            else
                if (mijloc - 1 != 1)
                    CautareBinara( cerinta, x, 1, mijloc - 1);
        }
    }
    fout << poz << '\n';
}

void Citire()
{
    ifstream fin("cautbin.in");
    int x, y;
    fin >> N;
    for ( int i = 1 ; i <= N ; ++i )
        fin >> v[i];
    fin >> M;
    for ( int i = 1 ; i <= M ; ++i )
    {
        fin >> x >> y;
        CautareBinara( x, y, 1, N );
    }
    fin.close();
}

int main()
{
    Citire();
    return 0;
}