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

  return 0;
}