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

int v[100001];

//classic binary search method
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;
    return -1;
}

//this method will provide the greatest position of the element in the array;
//if the element is not found then it will return -1;
int binarySearch0(int *v,int length,int val) {
 int i=-1,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;
    return -1;
}

//this method will return the largest position of the smallest element <= val
//it's guaranteed that the smallest number will be <= val
int binarySearch1(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;
    return i;
}

//this method will return the smallest position of the largest element <= val
//it's guaranteed that the smallest number will be <= val
int binarySearch2(int *v,int length,int val) {
     int i,step,ok=0;
    for(step=1;step<length;step=step<<1);
    for(i=0;step && !ok;step=step>>1) {
        if(i+step<length && *(v+(i+step))>val)
            i=i+step;
        if(*(v+(i+step)) == val) {
            ok=1;
            i=i+1;
        }
    }
    return i;
}

int main() {

    FILE *fin,*fout;
    fin=fopen("cautbin.in","r");
    fout=fopen("cautbin.out","w");

    int N,M,i,option,val,rez;
    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",&option);
        fscanf(fin,"%d",&val);

        switch(option) {
        case 0:
            rez = binarySearch0(v,N,val);
            fprintf(fout,"%d\n",rez+1);
            break;
        case 1:
             rez = binarySearch1(v,N,val);
            fprintf(fout,"%d\n",rez+1);
            break;
        case 2:
            rez = binarySearch2(v,N,val);
            fprintf(fout,"%d\n",rez+1);
            break;
        }

    }


    return 0;
}