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

//returns the largest position of val int the array or -1 if the val value is not in the array.
int binarySearch(int *v,int length,int val){
    int i,step;
    for(step=1;step<length;step=step<<1);
    for(i=0;step;step=step>>1)
        if(i+step < length && v[i+step] <= val)
            i=i+step;

    if(v[i] == val)
        return i+1;
    else if(v[i] < val)
        return i+1;
    return -1;
}

int binarySearch1(int *v,int length,int val){
    int i,step,ok=0;
    for(step=length-1;step>1;step=step>>1);
    for(i=-1;step < length && !ok;step=step<<1) {
        if(v[i+step] >= val)
            ok=1;
        i=i+step;
    }
    return i;
}

int v[1000000],N,M;
int main(void) {

    FILE *f1,*f2;
    f1=fopen("cautbin.in","r");
    f2=fopen("cautbin.out","w");

    int i,option,x,pos;

    fscanf(f1,"%d",&N);
    for(i=0;i<N;i++)
        fscanf(f1,"%d",&v[i]);
    fscanf(f1,"%d",&M);

    for(i=0;i<M;i++) {
        fscanf(f1,"%d%d",&option,&x);
        switch(option) {
            case 0:
                pos=binarySearch(v,N,x);
                fprintf(f2,"%d\n",pos);
            break;

            case 1:
                pos=binarySearch(v,N,x);
                fprintf(f2,"%d\n",pos);
            break;

            case 2:
                pos=binarySearch1(v,N,x);
                fprintf(f2,"%d\n",pos);
            break;
        }
    }

    return 0;
}