#include <stdio.h>
#include <stdlib.h>
int v[100000];
int cautBin1(int element,int n){
    int stanga,dreapta,mijloc;
    stanga=0;
    dreapta=n-1;
    while(dreapta-stanga>1){
        mijloc=(stanga+dreapta)/2;
        if(v[mijloc]>element)
            dreapta=mijloc;
        else
            stanga=mijloc;
    }
    if(element==v[stanga])
        return stanga;
    else
        return -1;
}
int cautBin2(int element,int n){
    int stanga,dreapta,mijloc;
    stanga=0;
    dreapta=n-1;
    while(dreapta-stanga>1){
        mijloc=(stanga+dreapta)/2;
        if(v[mijloc]>element)
            dreapta=mijloc;
        else
            stanga=mijloc;
    }
    return stanga;
}
int cautBin3(int element,int n){
    int stanga,dreapta,mijloc;
    stanga=0;
    dreapta=n-1;
    while(dreapta-stanga>1){
        mijloc=(stanga+dreapta)/2;
        if(v[mijloc]>element)
            dreapta=mijloc;
        else
            stanga=mijloc;
    }
    return stanga+1;
}
int main()
{
    FILE*fin,*fout;
    int n,i,nr,poz,cerinta,element;
    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" ,&nr);
    for(i=0;i<nr;i++){
        fscanf(fin, "%d%d" ,&cerinta,&element);
        if(cerinta==0){
            poz=cautBin1(element,n);
            if(poz==-1){
                fprintf(fout, "-1\n");
            }
            else{
                while(v[poz]==element && poz!=n)
                    poz++;
                fprintf(fout, "%d\n" ,poz); //la pozitie adaugi mereu 1
            }
        }
        else if(cerinta==1){
            poz=cautBin2(element,n);
            while(v[poz]<=element && poz!=n)
                poz++;
            fprintf(fout, "%d\n" ,poz);
        }
        else{
            poz=cautBin3(element,n);
            while(v[poz]>=element && poz>=0)
                poz--;
            fprintf(fout, "%d\n" ,poz+2);
        }
    }
    return 0;
}