#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int a[100005], c, x;
int cb0(int st, int dr, int k)
{
    int m;
    while(st <= dr)
    {
        m = (st + dr)/2;
        if(k >= a[m])
            st = m + 1;
        else
            dr = m - 1;
    }
    m = (st + dr)/2;
    if(a[m] > k) m --;
    if(a[m] == k)
          return m;
    return -1;
}
int cb1(int st, int dr, int k)
{
    int m;
    while(st < dr)
    {
        m = (st + dr)/2;
        if(k >= a[m])
            st = m + 1;
        else
            dr = m;
    }
    m = (st + dr)/2;
    if(a[m] > k) m --;
    return m;
}

int cb2(int st, int dr, int k)
{
    int m;
    while(st < dr)
    {
        m = (st + dr)/2;
        if(k > a[m])
            st = m + 1;
        else
            dr = m;
    }
    m = (st + dr)/2;
    if(a[m] < k) m ++;
    return m;
}
int main ()
{
    int i, m, n, t, v;
    f >> n;
    for(i = 1; i <= n; ++ i)
        f >> a[i];
    f >> m;
    for(i = 1; i <= m; ++ i)
    {
        f >> c >> x;
        if(c == 0)
            g << cb0(1, n, x) << "\n";
        if(c == 1)
            g << cb1(1, n, x) << "\n";
        if(c == 2)
            g << cb2(1, n, x) << "\n";
    }
    return 0;
}