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

int v[140000];

int calc(int cerinta, int x, int n){
    int poz, pas;
    poz=0;
    pas=1<<16;
    if(cerinta==1 || cerinta==0){
        while(pas!=0){
            if(poz+pas<n && v[poz+pas]<=x)
                poz+=pas;
            pas/=2;
        }
        if(v[poz]<x)
            return -2;
    }
    else
        while(pas!=0){
            if(poz+pas<n && v[poz+pas]<x)
                poz+=pas;
            pas/=2;
        }

    return poz;
}

int main(){
    FILE *fin, *fout;
    int n, m, i, caz, x, rez;
    fin=fopen("cautbin.in", "r");
    fout=fopen("cautbin.out", "w");
    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", &caz, &x);
        rez=calc(caz, x, n)+1;
        if(caz==0 || caz==1)
            fprintf(fout, "%d\n", rez);
        else
            fprintf(fout, "%d\n", rez+1);
    }
    fclose(fin);
    fclose(fout);

    return 0;
}