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

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;

    int st, dr, mij;
    int poz;
    for(int i = 0; i < m; i++) {

        fscanf(in, "%d %d", &type, &number);
        poz = -1;
        st = 1;
        dr = n;
        if(type < 2) {

            while(st <= dr) {

                mij = (st + dr) / 2;

                if(array[mij] == number) {

                    poz = mij;
                    st = mij + 1;

                } else if(array[mij] <= number) {

                    st = mij + 1;

                } else {

                    dr = mij - 1;

                }
            }
            if(type == 1 && poz > 0 && array[poz] > array[poz - 1])
                poz--;

            printf("%d\n", poz);
        } else {

            while(st <= dr) {

                mij = (st + dr) / 2;

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


            }

            printf("%d\n", st);



        }


    }
    return 0;
}