#include <fstream>
#include <algorithm>

using namespace std;

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

int n, m, i, t, x, st, dr, poz, mij, a[100005];

int main()
{
    f >> n;
    for(i = 1; i <= n; i++)
        f >> a[i];
    f >> m;
    while(m)
    {
        f >> t >> x;

        st = 1;
        dr = n;
        if(!t)
        {
            poz = -1;
            while(st <= dr)
            {
                mij = (st + dr) / 2;
                if(a[mij] < x)
                    st = mij + 1;
                else
                    if(a[mij] == x)
                    {
                        poz = max(poz, mij);
                        st = mij + 1;
                    }
                    else
                        dr = mij - 1;
            }
        }
        else
            if(t == 1)
            {
                poz = -1;
                while(st <= dr)
                {
                    mij = (st + dr) / 2;
                    if(a[mij] <= x)
                    {
                        poz = max(poz, mij);
                        st = mij + 1;
                    }
                    else
                        dr = mij - 1;
                }
            }
            else
            {
                poz = n + 1;
                while(st <= dr)
                {
                    mij = (st + dr) / 2;
                    if(a[mij] < x)
                        st = mij + 1;
                    else
                    {
                        poz = min(poz, mij);
                        dr = mij - 1;
                    }
                }
                if(poz == n + 1)
                    poz = -1;
            }

        g << poz << '\n';

        m--;
    }

    f.close();
    g.close();

    return 0;
}