#include <stdio.h>

FILE *fin;
FILE *fout;

int  v[100000];

int main() {

    fin=fopen("cautbin.in", "r");
    fout=fopen("cautbin.out", "w");

    int n, m, i, ce, st, dr, gasit, mijloc;
    int x;
    fscanf(fin, "%d", &n);

    for (i=0; i<n; i++){
        fscanf(fin, "%d", &v[i]);
        //fprintf(fout, "%lu ", v[i]);
    }
    //fprintf(fout, "\n ");
    fscanf(fin, "%d", &m);

    for (i=0; i<m; i++){
        fscanf(fin, "%d%d", &ce, &x);
        st=0;
        dr=n-1;
        gasit=0;
        while (st <= dr && gasit != 1){
            mijloc=(st+dr)/2;
            //fprintf(fout, "st=%d, dr=%d, mijloc=%d v[mijloc]=%lu\n", st, dr, mijloc, v[mijloc]);
            if (v[mijloc] == x){
                gasit=1;
            } else if (v[mijloc] > x){
                dr=mijloc-1;
            } else if (v[mijloc] < x){
                st=mijloc+1;
            }
        }
        //fprintf(fout, "gasit=%d mijloc=%d\n", gasit, mijloc);
        if (ce == 0){
            if (gasit== 0){
                fprintf(fout, "-1\n");
            } else {
                while (v[mijloc] == x){
                    mijloc++;
                }
                fprintf(fout, "%d\n", mijloc);
            }
        } else if (ce == 1){
            while (v[mijloc] <= x){
                mijloc++;
            }
            fprintf(fout, "%d\n", mijloc);
        } else {
            if (gasit == 0){
                fprintf(fout, "%d\n", mijloc+2);
            } else {
                while (v[mijloc] == x && v[mijloc-1] == x){
                    mijloc--;
                }
                fprintf(fout, "%d\n", mijloc+1);
            }
        }
    }
    fclose(fin);
    fclose(fout);

    return 0;
}