#include <cstdio>
#define N 100010
using namespace std;
int v[N];
int bsearch0(int p, int u, int val)
{
    int  m;
    while(p <= u)
    {
        m = (p + u) / 2;
        if(v[m] <= val)
            p = m + 1;
        else u = m - 1;
    }
    m = (p + u) / 2;
    if(v[m] > val) m --;
    if(v[m] == val) return m;
    return - 1;
}
int bsearch1(int p, int u, int val)
{
    int m;
    while(p < u)
    {
        m = (p + u) / 2;
        if(v[m] <= val)
            p = m + 1;
        else u = m;
    }
    m = (p + u) / 2;
    if(v[m] > val) m--;
    return m;
}
int bsearch2(int p, int u, int val)
{
    int m;
    while(p < u)
    {
        m = (p + u) / 2;
        if(v[m] < val)
            p = m + 1;
        else u = m;
    }
    m = (p + u) / 2;
    if(v[m] < val)
        m ++;
    return m;
}
int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    int i, n, m, tip ,val;
    scanf("%d", &n);
    for(i = 1; i<=n; i++)
        scanf("%d", &v[i]);
    scanf("%d", &m);
    for(i = 1; i<=m; i++)
    {
        scanf("%d%d", &tip, &val);
        if(tip == 0) printf("%d\n", bsearch0(1, n, val));
        if(tip == 1) printf("%d\n", bsearch1(1, n, val));
        if(tip == 2) printf("%d\n", bsearch2(1, n, val));
    }
    return 0;
}