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

int V[100000];

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