#include <stdio.h>
#include <stdlib.h>

int binarySearch(int x, int i1, int i2, int * elements){
    if(i1 > i2) return -1;

    int new_i = i1 + (i2-i1)/2;

    if( elements[new_i] == x ){
        return new_i;
    } else if(elements[new_i] < x){
        return binarySearch(x, new_i+1, i2, elements);
    } else { // the element under the new index is bigger than x
        return binarySearch(x, i1, new_i-1, elements);
    }
}

int biggestPositionOfX(int x, int i1, int i2, int * elements){
    int pos = binarySearch(x, i1, i2, elements);
    if (pos == -1){
        return -1;
    } else {
        int retval = biggestPositionOfX(x, pos+1, i2, elements);
        if(retval == -1){
            return ++pos;
        } else {
            return retval;
        }
    }
}

int binarySearch2(int x, int i1, int i2, int * elements){
    if(i1 > i2) {
        return -1 * i2; // i2 is the index of the nearest left element
    }

    int new_i = i1 + (i2-i1)/2;

    if( elements[new_i] == x ){
        return new_i;
    } else if(elements[new_i] < x){
        return binarySearch2(x, new_i+1, i2, elements);
    } else { // the element under the new index is bigger than x
        return binarySearch2(x, i1, new_i-1, elements);
    }
}

int biggestPositionOfValueLowerOrEqual(int x, int i1, int i2, int * elements){
    int pos = binarySearch2(x, i1, i2, elements);
    if(pos < 0){
        return pos * -1 + 1;
    } else {
        int retval = biggestPositionOfX(x, pos+1, i2, elements);
        if(elements[pos+1]>x || retval == -1){
            return ++pos;
        } else {
            return retval;
        }
    }
}

int binarySearch3(int x, int i1, int i2, int * elements){
    if(i1 > i2) return -1 * i1; // i1 is the index of the nearest right element

    int new_i = i1 + (i2-i1)/2;

    if( elements[new_i] == x ){
        return new_i;
    } else if(elements[new_i] < x){
        return binarySearch3(x, new_i+1, i2, elements);
    } else { // the element under the new index is bigger than x
        return binarySearch3(x, i1, new_i-1, elements);
    }
}

int lowestPositionOfX(int x, int i1, int i2, int * elements){
    int pos = binarySearch(x, i1, i2, elements);
    if (pos == -1){
        return -1;
    } else {
        int retval = lowestPositionOfX(x, i1, pos-1, elements);
        if(retval == -1){
            return ++pos;
        } else {
            return retval;
        }
    }
}
int lowestPositionOfValueLowerOrEqual(int x, int i1, int i2, int * elements){
    int pos = binarySearch3(x, i1, i2, elements);
    if(pos < 0){
        return pos * -1 + 1;
    } else {
        int retval = lowestPositionOfX(x, i1, pos-1, elements);
        if(elements[pos+1]>x || retval == -1){
            return ++pos;
        } else {
            return retval;
        }
    }
}



int main(){
    int N,M, i, x;

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

    scanf("%i", &N);
    int list[N];
    for(i=0; i<N; i++){
        scanf("%i", &list[i]);
    }

    scanf("%i", &M);
    int tip;
    for(i=0; i<M; i++){
        scanf("%i %i", &tip, &x);
        switch(tip){
            case 0:
                // the biggest position of the value of x, or -1 if it is not found on the list
                printf("%i\n", biggestPositionOfX(x, 0, N-1, list) );
                break;
            case 1:
                // the biggest position of a value lower than or equal with x
                printf("%i\n", biggestPositionOfValueLowerOrEqual(x, 0, N-1, list) );
                break;
            case 2:
                // the lowest position of a value bigger than or equal with x
                printf("%i\n", lowestPositionOfValueLowerOrEqual(x, 0, N-1, list) );
                break;
        }
    }

    return 0;
}