#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
long long n, m, v[100000 + 5];
int main()
{
    int c, x, i;
    fin >> n;
    for ( i = 1; i <= n; ++i )
        fin >> v[i];

    fin >> m;
    for ( i = 1; i <= m; ++i )
    {
        fin >> c >> x;
        int st = 1, dr  = n, mij, sol = -1;
        if ( c == 0)
        {
            while (st <= dr )
            {
                mij = (st + dr) / 2;
                if ( v[mij] == x )
                    sol = mij;

                if ( v[mij] <= x )
                    st = mij + 1;
                else
                    dr = mij - 1;
            }
            fout << sol << endl;
        }
        if ( c == 1 )
        {
            while (st <= dr )
            {
                mij = (st + dr) / 2;

                if ( v[mij] <= x )
                {
                    sol = mij;
                    st = mij + 1;
                }
                else
                    dr = mij - 1;
            }
            fout << sol << endl;
        }
        if ( c == 2 )
        {
            while (st <= dr )
            {
                mij = (st + dr) / 2;

                if ( v[mij] >= x )
                {
                    sol = mij;
                    dr = mij - 1;
                }
                else
                    st = mij + 1;
            }
            fout << sol << endl;
        }
    }

    return 0;
}