#include <iostream>
#include <fstream>

using namespace std;

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

int a[100001], n, m, x, p, y;

int cbin( int st, int dr )
{
    if( st == dr )
        return st;
    else
    {
        int mij = st + ( dr - st )/2;

        if( x <= a[mij] )
            return cbin( st, mij);
        else
            return cbin( mij + 1, dr );
    }
}

int main()
{
    in >> n;
    for( int i = 1; i <= n; i ++ )
    {
        in >> a[i];
    }
    in >> m;
    for( int i = 1; i <= m; i ++ )
    {
        in >> y >> x;
        p = cbin( 1, n );
        if( y == 0 )
        {
            if( x != a[p] )
                out << -1 << '\n';
            else
            {
                while( p < n && a[p+1] == x )
                    p++;
                out << p << '\n';
            }
        }
        else if ( y == 1 )
        {
            if( a[p] <= x )
            {
                while( p < n && a[p+1] <= x )
                    p++;
                out << p << '\n';
            }
            else
            {
                while( a[p] > x )
                    p --;
                out << p << '\n';
            }
        }
        else if( y == 2 )
        {
            if( a[p] >= x )
            {
                while( p > 0 && a[p-1] >= x )
                    p--;
                out << p << '\n';
            }
            else
            {
                while( a[p] < x )
                    p ++;
                out << p << '\n';
            }
        }

    }
    return 0;
}