#include <iostream>
#include <fstream>
using namespace std;

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

long long n, m, a[100001], x, i, p, st, dr, mij;

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

    f >> m;
    for (i=1; i<=m; i++)
    {
        f >> p >> x;
        st = 1;
        dr = n;

        if (p == 0)
        {
            while (st <= dr)
            {
                mij = (st + dr) / 2;
                if (x >= a[mij])
                    st = mij + 1;
                else
                    dr = mij - 1;
            }
            if (x == a[st-1])
                g << st - 1 << "\n";
            else
                g << -1 << "\n";
        }

        if (p == 1)
        {
            while (st <= dr)
            {
                mij = (st + dr) / 2;
                if (x >= a[mij])
                    st = mij + 1;
                else
                    dr = mij - 1;
            }
            g << st - 1 << "\n";
        }

        if (p == 2)
        {
            while(st <= dr)
            {
                mij = (st + dr) / 2;
                if (x <= a[mij])
                    dr = mij - 1;
                else
                    st = mij + 1;
            }
            g << dr + 1<< "\n";
        }

    }

    return 0;
}