#include<cstdio>
using namespace std;

const int NMAX = 100009;
int n, m, type, key, v[NMAX];

inline int cauta0(int st, int dr, int x)
{
    int m;
    while(st <= dr)
    {
        m = (st + dr) >> 1;
        if(v[m] <= x) st = m + 1;
        else dr = m - 1;
    }
    if(v[m] > x) --m;
    if(v[m] == x) return m;
    return -1;
}

inline int cauta1(int st, int dr, int x)
{
    int m;
    while(st <= dr)
    {
        m = (st + dr) >> 1;
        if(v[m] <= x) st = m + 1;
        else
        dr = m - 1;
    }
    if(v[m] > x) -- m;
    return m;
}

inline int cauta2(int st, int dr, int x)
{
    int m;
    while(st <= dr)
    {
        m = (st + dr) >> 1;
        if(v[m] >= x) dr = m - 1;
        else st = m + 1;
    }
    if(v[m] < x) --m;
    return m;
}
int main()
{
    freopen("cautbin.in", "rt", stdin); freopen("cautbin.out", "wt", stdout);

    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &v[i]);
    scanf("%d", &m);
    while(m--)
    {
        scanf("%d%d", &type, &key);
        if(!type) printf("%d\n", cauta0(1, n, key));
        else
        if(type == 1) printf("%d\n", cauta1(1, n, key));
        else printf("%d\n", cauta2(1, n, key));
    }
}