#include <cstdio>

int n, m;
int v[100005];

int search_1(int x);
int search_2(int x);
int search_3(int x);

int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

    scanf("%d", &n);
    for (int i=1; i<=n; ++i){
        scanf("%d", &v[i]);
    }
    scanf("%d", &m);
    for (int i=0; i<m; ++i){
        int r, x;

        scanf("%d %d", &r, &x);
        switch (r){
            case 0:
                printf("%d\n", search_1(x));
                break;
            case 1:
                printf("%d\n", search_2(x));
                break;
            case 2:
                printf("%d\n", search_3(x));
                break;
        }
    }
    return 0;
}

int search_1(int x){
    int li=1, ls=n, m;

    while (li<=ls){
        m = (li+ls)/2;

        if (v[m] <= x){
            li = m+1;
        }
        else{
            ls = m-1;
        }
    }
    m=(li+ls)/2;
    if (v[m]>x)
        --m;
    if (v[m]==x){
        return m;
    }
    else{
        return -1;
    }
}

int search_2(int x){
    int li=1, ls=n, m;

    while (li<=ls){
        m = (li+ls)/2;

        if (v[m] <= x){
            li = m+1;
        }
        else{
            ls = m-1;
        }
    }
    m=(li+ls)/2;
    if (v[m]>x)
        --m;
    return m;
}

int search_3(int x){
    int li=1, ls=n, m;

    while (li<=ls){
        m = (li+ls)/2;

        if (v[m] >= x){
            ls = m-1;
        }
        else{
            li = m+1;
        }
    }
    m=(li+ls)/2;
    if (v[m]<x)
        ++m;
    return m;
}