#include <cstdio>

int n, m;
int v[100001]={};

int binary_1(int x);
int binary_2(int x);
int binary_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 c, x;

        scanf("%d %d", &c, &x);
        switch (c){
        case 0:
            printf("%d\n", binary_1(x));
            break;
        case 1:
            printf("%d\n", binary_2(x));
            break;
        case 2:
            printf("%d\n", binary_3(x));
            break;
        }
    }
    return 0;
}

int binary_1(int x){
    int li=0, ls=n-1, 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;
    return -1;
}


int binary_2(int x){
    int li=0, ls=n-1, m;

    while (li<=ls){
        int 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 binary_3(int x){
    int li=0, ls=n-1, m;

    while (li<=ls){
        int 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;
}