#include <bits/stdc++.h>
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

const int NMAX = 100005;

int n, m, a[NMAX];

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

    fin >> m;
    while (m--)
    {
        int op, x;
        fin >> op >> x;

        if (op == 0)
        {
            int st = 1, dr = n, poz = -1;
            while (st <= dr)
            {
                int mij = (st + dr) / 2;

                if (a[mij] <= x)
                {
                    poz = mij;
                    st = mij + 1;
                }
                else dr = mij - 1;
            }

            if (poz > 0 && a[poz] != x) poz = -1;
            fout << poz << "\n";
        }

        if (op == 1)
        {
            int st = 1, dr = n, poz = -1;
            while (st <= dr)
            {
                int mij = (st + dr) / 2;

                if (a[mij] <= x)
                {
                    poz = mij;
                    st = mij + 1;
                }
                else dr = mij - 1;
            }

            fout << poz << "\n";
        }

        if (op == 2)
        {
            int st = 1, dr = n, poz = -1;
            while (st <= dr)
            {
                int mij = (st + dr) / 2;

                if (a[mij] >= x)
                {
                    poz = mij;
                    dr = mij - 1;
                }
                else st = mij + 1;
            }

            fout << poz << "\n";
        }
    }
    return 0;
}