#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int *a;
int binsearch0(int p, int q, int k)
{
    int m;
    while(p <= q)
    {
        m = (p + q)/2;
        if(k >= a[m])
            p = m + 1;
        else
            q = m - 1;
    }
    m = (p + q)/2;
    if(a[m] > k)
    {
        m --;
    }
    if(a[m] == k)
        return m;
    return -1;
}
int binsearch1(int p, int q, int k)
{
    int m;
    while(p < q)
    {
        m = (p + q)/2;
        if(k >= a[m])
            p = m + 1;
        else
            q = m;
    }
    m = (p + q)/2;
    if(a[m] > k)
    {
        m --;
    }
    return m;
}
int binsearch2(int p, int q, int k)
{
    int m;
    while(p < q)
    {
        m = (p + q)/2;
        if(k > a[m])
            p = m + 1;
        else
            q = m;
    }
    m = (p + q)/2;
    if(a[m] < k)
    {
        m ++;
    }
    return m;
}
int main ()
{
    int i, m, n, t, v;
    f >> n;
    a = new int[n + 1];
    for(i = 1; i <= n; ++ i)
    {
        f >> a[i];
    }
    f >> m;
    for(i = 1; i <= m; ++ i)
    {
        f >> t >> v;
        if(t == 0)
            g << binsearch0(1, n, v) << "\n";
        if(t == 1)
            g << binsearch1(1, n, v) << "\n";
        if(t == 2)
            g << binsearch2(1, n, v) << "\n";
    }
    delete[] a;
    return 0;
}