#include <iostream>
#include <fstream>

using namespace std;

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

int a[100005], n;

int rezolvare0(int);
int rezolvare1(int);
int rezolvare2(int);

int main()
{
    int m, i, v, x;
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i];
    fin >> m;
    while (m)
    {
        fin >> v >> x;
        if (v == 0)
            fout << rezolvare0(x) << " \n";
        else if (v == 1)
            fout << rezolvare1(x) << " \n";
        else
            fout << rezolvare2(x) << " \n";
        m--;
    }
    fin.close();
    fout.close();
    return 0;
}

int rezolvare0(int x)
{
    int dr, st, m, y;
    dr = n;
    st = 1;
    y = 0;
    while (st <= dr)
    {
        m = (dr + st) / 2;
        if (x >= a[m])
            st = m + 1;
        else
            dr = m - 1;
        if (x == a[m])
            y = 1;
    }
    if (y)
        return dr;
    else
        return -1;
}

int rezolvare1(int x)
{
    int dr, st, m;
    dr = n;
    st = 1;
    while (st <= dr)
    {
        m = (dr + st) / 2;
        if (x >= a[m])
            st = m + 1;
        else
            dr = m - 1;
    }
    return dr;
}

int rezolvare2(int x)
{
    int dr, st, m;
    dr = n;
    st = 1;
    while (st <= dr)
    {
        m = (dr + st) / 2;
        if (x <= a[m])
            dr = m - 1;
        else
            st = m + 1;
    }
    return st;
}