#include <stdio.h>
#include <math.h>

int sir[100000];

int main()
{
    FILE *fin, *fout;
    int n, m, i, st, mij, dr, x, nr;
    fin=fopen("cautbin.in", "r");
    fscanf(fin, "%d", &n);
    for(i=0; i<n; i++)
        fscanf(fin, "%d", &sir[i]);
    fscanf(fin, "%d", &m);
    fout=fopen("cautbin.out", "w");
    for(i=0; i<m; i++){
        fscanf(fin, "%d%d", &x, &nr);
        if(x==0){
            st=0;
            dr=n;
            while(dr-st>1){
                mij=(st+dr)/2;
                if(sir[mij]>nr)
                    dr=mij;
                else
                    st=mij;
            }
            if(nr==sir[st])
                fprintf(fout, "%d", st+1);
            else
                fprintf(fout, "-1");
        }else if(x==1){
            st=0;
            dr=n;
            while(dr-st>1){
                mij=(st+dr)/2;
                if(sir[mij]>nr)
                    dr=mij;
                else
                    st=mij;
            }
            fprintf(fout, "%d", st+1);
        }else{
            st=-1;
            dr=n-1;
            while(dr-st>1){
                mij=(st+dr)/2;
                if(sir[mij]<nr)
                    st=mij;
                else
                    dr=mij;
            }
            fprintf(fout, "%d", st+2);
        }
        fprintf(fout, "\n");
    }
    fclose(fin);
    fclose(fout);
    return 0;
}