#include <iostream>
#include <fstream>

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

#define nMAX 100005

int n, T, v[ nMAX ], i, logn, lg, tip, x;

int main()
{
    fin>> n;
    for ( i = 1 ; i <= n; i++ )
    {
        fin>> v[ i ];
    }
    fin>> T;

    for ( logn = 1; logn <= n; logn <<= 1 );

    for ( ; T; T-- )
    {
        fin>>tip>>x;
        if ( tip <= 1 )
        {
            for ( i = 0, lg = logn; lg; lg >>= 1 )
            {
                if ( i + lg <= n && v[ i + lg ] <= x )
                {
                    i += lg;
                }
            }
            if ( tip == 0 && v[ i ] != x )
                fout<< -1 << '\n';
            else
                fout<< i << '\n';
        }
        else if ( tip == 2 )
        {
            for ( i = n, lg = logn ; lg ; lg >>= 1 )
            {
                if ( i - lg > 0 && v[ i - lg ] >= x )
                    i -= lg;
            }
            fout<< i << '\n';
        }
    }

    return 0;
}