#include<stdio.h>
#define VMAX 100005
int v[VMAX];

int cautbin0(int v[],int n,int x){
    int st=0,dr=n-1,mij;
    while(st<=dr){
        mij=(st+dr)/2;
        if(v[mij]<=x) st=mij+1;
        else dr=mij-1;
    }
    if(dr>=0&&v[dr]==x) return dr+1;
    return -1;
}
int cautbin1(int v[],int n,int x){
    int st=0,dr=n-1,mij;
    while(st<=dr){
        mij=(st+dr)/2;
        if(v[mij]<=x) st=mij+1;
        else dr=mij-1;
    }
    return dr+1;
}

int cautbin2(int v[],int n,int x){
    int st=0,dr=n-1,mij;
    while(st<=dr){
        mij=(st+dr)/2;
        if(v[mij]<x) st=mij+1;
        else dr=mij-1;
    }
    return st+1;
}

int main(void){
    FILE*fin=fopen("cautbin.in","r");
    FILE*fout=fopen("cautbin.out","w");
    int n,h,m,k;
    fscanf(fin,"%d",&n);
    for(int i=0;i<n;i++) {
        fscanf(fin,"%d",&v[i]);
    }
    fscanf(fin,"%d",&h);

    for(int i=0;i<h;i++){
        fscanf(fin,"%d %d",&m,&k);
        int res;
        if(m==0) {
            res=cautbin0(v,n,k);
        }
        else if(m==1) {
            res=cautbin1(v,n,k);
        }
        else{
            res=cautbin2(v,n,k);
        }
        fprintf(fout,"%d\n",res);
    }

    fclose(fin);
    fclose(fout);
    return 0;
}