#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=0; 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)+1);
            break;
        case 1:
            printf("%d\n", binary_2(x)+1);
            break;
        case 2:
            printf("%d\n", binary_3(x)+1);
            break;
        }
    }
    return 0;
}

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

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


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

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

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

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