#include <fstream>

using namespace std;

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

int n, i, j, k, x, c;
int a[100005];

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

    for (f >> k; k; k--)
    {
        f >> c >> x;
        if (c == 0)
        {
            int st = 1, dr = n, m;
            while (st <= dr)
            {
                m = (st+dr)/2;
                if (a[m] > x)
                    dr = m-1;
                else
                    st = m+1;
            }
            m = (st+dr)/2;
            if (a[m] == x)
                g << m << '\n';
            else
                g << "-1\n";
        }
        else if (c == 1)
        {
            int st = 1, dr = n, m;
            while (st <= dr)
            {
                m = (st+dr)/2;
                if (a[m] > x)
                    dr = m-1;
                else
                    st = m+1;
            }
            m = (st+dr)/2;
            if (a[m] > x)
                m--;
            g << m << '\n';
        }
        else
        {
            int st = 1, dr = n, m;
            while (st <= dr)
            {
                m = (st+dr)/2;
                if (a[m] >= x)
                    dr = m-1;
                else
                    st = m+1;
            }
            m = (st+dr)/2;
            if (a[m] < x)
                m++;
            g << m << '\n';
        }
    }
}