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

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

int 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 << "\n";
            }
        }

        return 0;
    }

}