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

int v[100001];

int lwr_bound (int st, int dr, int val)
{
    int med, last = -1;
    while (st <= dr)
    {
        med = (st + dr) / 2;
        if (v[med] >= val)
        {
            dr = med - 1;
            last = med;
        }
        else
            st = med + 1;
    }
    return last;
}

int upr_bound (int st, int dr, int val)
{
    int med, last = -1;
    while (st <= dr)
    {
        med = (st + dr) / 2;
        if (v[med] <= val)
        {
            st = med + 1;
            last = med;
        }
        else
            dr = med - 1;
    }
    return last;
}

int main()
{
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");
    int n, i, tip, x, aux, m;
    in >> n;
    for (i = 0; i < n; i++)
        in >> v[i];
    in >> m;
    for (i = 0; i < m; i++)
    {
        in >> tip >> x;
        if (tip == 0)
        {
            aux = upr_bound(0, n - 1, x);
            if (tip != -1 && v[aux] == x)
                out << aux + 1 << "\n";
            else
                out << "-1\n";
        }
        else if (tip == 1)
            out << upr_bound(0, n - 1, x) + 1<< "\n";
        else
            out << lwr_bound(0, n - 1, x) + 1 << "\n";
    }
    return 0;
}