#include<stdio.h>
using namespace std;
int v[2000005];
int caut1(int a, int b, int x){
    int m;
    while (a <= b) {
        m = (a + b) / 2;
        if (v[m] <= x)
            a = m + 1;
        else
            b = m - 1;
    }
    m = (a + b) / 2;

    if (v[m] > x) m --;
    if (v[m] == x)
        return m;
    return -1;
}
int caut2(int a, int b, int x){
    int m;
    while (a < b) {
        m = (a + b) / 2;
        if (v[m] <= x)
            a = m + 1;
        else
            b = m;
    }
    m = (a + b) / 2;

    if (v[m] > x) m --;
        return m;
}
int caut3(int a, int b, int x){
    int m;
    while (a < b) {
        m = (a + b) / 2;
        if (v[m] < x)
            a = m + 1;
        else
            b = m;
    }
    m = (a + b) / 2;

    if (v[m] < x) m ++;
        return m;
}
int main()
{
    int i, n, m, p, x;
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    scanf("%d", &n);
    for (i = 1; i <= n; ++ i)
        scanf("%d", &v[i]);
    scanf("%d", &m);
    while (m --){
        scanf("%d%d", &p, &x);
        if (p == 0)
             printf("%d\n", caut1(1, n, x));
        if (p == 1)
             printf("%d\n", caut2(1, n, x));
        if (p == 2)
             printf("%d\n", caut3(1, n, x));
    }
}