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

int bs0(int* array, int n, int number) {

    int pos = -1;
    int st = 1, dr = n, mij;

    while(st <= dr) {

        mij = (st + dr) / 2;
        if(array[mij] == number) {

            pos = mij;
            st = mij + 1;
            continue;

        }

        if(array[mij] < number)
            st = mij + 1;
        else
            dr = mij - 1;

    }

    return pos;
}

int bs1(int* array, int n, int number) {

    int st = 1, dr = n, mij;

    while(st <= dr) {

        mij = (st + dr) / 2;
        if(array[mij] <= number) {

            st = mij + 1;

        } else {

            dr = mij - 1;

        }
    }

    return dr;

}

int bs2(int* array, int n, int number) {

    int st = 1, dr = n, mij;

    while(st <= dr) {

        mij = (st + dr) / 2;

        if(array[mij] < number)
            st = mij + 1;
        else
            dr = mij - 1;

    }

    return st;
}

int main() {
    FILE* in = fopen("cautbin.in", "r");
    FILE* out = fopen("cautbin.out", "w");

    int n;
    fscanf(in, "%d", &n);

    int* array = (int*)malloc(sizeof(int) * (n + 1));

    for(int i = 1; i <= n; i++)
        fscanf(in, "%d", &array[i]);

    int m;
    fscanf(in, "%d", &m);

    int type, number;

    for(int i = 0; i < m; i++) {

        fscanf(in, "%d %d", &type, &number);

        switch(type) {

            case 0:
                fprintf(out, "%d\n", bs0(array, n, number));
                break;

            case 1:
                fprintf(out, "%d\n", bs1(array, n, number));
                break;

            case 2:
                fprintf(out, "%d\n", bs2(array, n, number));
                break;


        }

    }
    return 0;
}