#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
#define NMAX 100005
int n, m, v[NMAX], put = 1;
void citire()
{
    f >> n;
    for (int i = 1; i <= n; ++i)
        f >> v[i];
    while (put < n)
        put <<= 1;
}
int cautare_binara0(int x)
{
    int i = 0;
    for (int l = put; l > 0; l >>= 1)
        if (i + l <= n && x >= v[i + l])
            i += l;
    if (v[i] == x)
        return i;
    return -1;
}
int cautare_binara1(int x)
{
    int i = 0;
    for (int l = put; l > 0; l >>= 1)
        if (i + l <= n && x >= v[i + l])
            i += l;
    return i;
}
int cautare_binara2(int x)
{
    int i = 0;
    for (int l = put; l > 0; l >>= 1)
        if (i + l <= n && x > v[i + l])
            i += l;
    return i + 1;
}
void rezolvare()
{
    f >> m;
    int tip, x;
    for (int i = 1; i <= m; ++i)
    {
        f >> tip >> x;
        if (tip == 0)
            g << cautare_binara0(x) << '\n';
        else if (tip == 1)
            g << cautare_binara1(x) << '\n';
        else
            g << cautare_binara2(x) << '\n';
    }
}
int main()
{
    citire();
    rezolvare();
    return 0;
}