#include <stdio.h>

#define TYPE_0 0
#define TYPE_1 1
#define TYPE_2 2
#define NOT_FOUND -1
#define MAX_N 100001

int V[MAX_N];

int binary_search0(int left, int right, int x)
{
    int last = 0;
    for (; left < right; ) {
        int mid = left + (right - left) / 2;
        if (V[mid] <= x) {
            last = mid;
            left = mid;
        } else right = mid - 1;
    }

    if (V[last] == x) return last;
    else return NOT_FOUND; 
}

int binary_search1(int left, int right, int x)
{
    int last = 0;
    for (; left < right; ) {
        int mid = left + (right - left) / 2;
        if (V[mid] <= x) {
            last = mid;
            left = mid;
        } else right = mid - 1;
    }
    
    return last;
}

int binary_search2(int left, int right, int x)
{
    int last = 0;
    for (; left < right; ) {
        int mid = left + (right - left) / 2;
        if (V[mid] >= x) {
            last = mid;
            right = mid;
        } else left = mid + 1;
    }

    return last;
}

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

    int N;
    fscanf(fdin, "%d", &N);

    int i;
    for (i = 0; i < N; i++) fscanf(fdin, "%d", &V[i]);

    int op_number;
    fscanf(fdin, "%d", &op_number);
    int op_type, x, operation;
    for (operation = 1; operation <= op_number; operation++) {
        fscanf(fdin, "%d%d", &op_type, &x);
        switch(op_type) {
            case TYPE_0 :
                fprintf(fdout, "%d\n", binary_search0(0, N, x) + 1);
                break;
            case TYPE_1 :
                fprintf(fdout, "%d\n", binary_search1(0, N, x) + 1);
                break;
            case TYPE_2 :
                fprintf(fdout, "%d\n", binary_search2(0, N, x) + 1);
                break;
            default :
                fprintf(fdout, "Don't give me stupid indexes\n");
        }

    }

    fclose(fdin);
    fclose(fdout);

    return 0;
}