#include <iostream>
#include <fstream>

using namespace std;

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

int v[100010];

int main()
{
    int n,m,t,x;
    in >> n;
    for (int i = 1; i<=n; i++)
        in >> v[i];
    in >> m;
    for (int a = 1; a<=m; a++)
    {
        in >> t >> x;
        if (t == 0)
        {
            int mij, p = 1, u = n;
            while (p <= u)
            {
                mij = (p + u) / 2;
                if (v[mij] <= x)
                    p = mij + 1;
                else
                    u = mij - 1;
            }
            mij = (p + u) / 2;

            if (v[mij] > x) mij --;
            if (v[mij] == x)
                out << mij << "\n";
            else
                out << "-1\n";
        }
        if (t == 1)
        {
            int mij, p = 1, u = n;
            while (p < u)
            {
                mij = (p + u) / 2;
                if (v[mij] <= x)
                    p = mij + 1;
                else
                    u = mij;
            }
            mij = (p + u) / 2;
            if (v[mij] > x)
                mij--;
            out << mij << "\n";
        }
        if (t == 2)
        {
            int mij, p = 1, u = n;
            while (p < u)
            {
                mij = (p + u) / 2;
                if (v[mij] < x)
                    p = mij + 1;
                else
                    u = mij;
            }
            mij = (p + u) / 2;
            if (v[mij] < x) mij ++;
            out << mij << "\n";
        }
    }
}