#include <stdio.h>
#include <stdlib.h>
#define NMAX 100000
int v[NMAX];
int n,c,x;
int cautareBinara(){
    int st,dr,mij;
    if(c==0){
        st=0;
        dr=n;
        while(dr-st>1){
            mij=st+(dr-st)/2;
            if(v[mij]>x){
                dr=mij;
            }else
                st=mij;
        }
        if(v[st]==x)
            return st;
        return -1;
    }
    if(c==1){
        st=0;
        dr=n-1;
        while(dr-st>1){
            mij=st+(dr-st)/2;
            if(v[mij]>x){
                dr=mij;
            }else
                st=mij;
        }
        return st;
    }
    st=-1;
    dr=n-1;
    while(dr-st>1){
        mij=st+(dr-st)/2;
        if(v[mij]<x){
            dr=mij;
        }else
            st=mij;
    }
    return st;
}
int main(){
    FILE *fin,*fout;
    int m,i;
    fin=fopen("cautbin.in","r");
    fscanf(fin,"%d",&n);
    for(i=0;i<n;i++){
        fscanf(fin,"%d",&v[i]);
    }
    fscanf(fin,"%d",&m);
    fout=fopen("cautbin.out","w");
    for(i=0;i<m;i++){
        fscanf(fin,"%d%d",&c,&x);
        fprintf(fout,"%d\n",cautareBinara());
    }
    return 0;
}