#include <fstream>
#include <algorithm>

int main()
{
    int* p;
    static int v[100001];
    int n, m, i, t, x;
    std::ifstream fi("cautbin.in");
    std::ofstream fo("cautbin.out");
    fi >> n;
    for (i = 0; i < n; i++)
        fi >> v[i];
    fi >> m;
    while (m--)
    {
        fi >> t >> x;
        if (t == 0)
        {
            p = std::upper_bound(v, v + n, x) - 1;
            fo << ((*p == x) ? (p - v + 1) : -1) << '\n';
        }
        else if (t == 1)
        {
            p = std::upper_bound(v, v + n, x) - 1;
            fo << (p - v + 1) << '\n';
        }
        else if (t == 2)
        {
            p = std::lower_bound(v, v + n, x);
            fo << (p - v + 1) << '\n';
        }
    }
}
/*
int main()
{
    while (true) std::cout << '.' << '.' << '.' << '.' << '\b' << '\b' << '\b' << '\b';
}
*/

/*

int pow10(int n)
{
    int j = 1, d = 0;
    while (d < n)
    {
        j *= 10;
    }
    return j;
}

long long baza2(int n)
{
    long long c, r, x = 0, f = 0;
    c = n;
    while (c)
    {
        r = c % 2;
        if (r == 0) f++;
        x = x * 10 + r;
        c = c / 2;
    }
    x = x * (long long)(pow10(f));
    return x;
}

*/

/*
bool isPrime(int n)
{
    int i;
    if (n == 2) return true;
    if (n == 1 || !(n & 1)) return false;
    for (i = 3; i * i <= n; i += 2)
        if (!(n % i)) return false;
    return true;
}
*/

//std::ifstream fi("nrapprime.in");
//std::ofstream fo("nrapprime.out");