#include <stdio.h>
#include <stdlib.h>
#define L 16
#define N 100000
int v[N];
int cautbin0(int x){
    int pas, r;
    pas = 1<<L;
    r=0;
    while(pas!=0){
        if(v[r+pas]<=x)
            r+=pas;
        pas/=2;
    }
    if(v[r+pas] == x)
        return r;
    else
        return -1;
}
int cautbin1(int x){
    int pas, r;
    pas = 1<<L;
    r=0;
    while(pas!=0){
        if(v[r+pas]<=x)
            r+=pas;
        pas/=2;
    }
    return r;
}
int cautbin2(int x){
    int pas, r;
    pas = 1<<L;
    r=0;
    while(pas!=0){
        if(!(v[r+pas]>=x))
            r+=pas;
        pas/=2;
    }
    return r++;
}
int main()
{
    FILE *f1 = fopen("cautbin.in","r"), *f2 = fopen("cautbin.out","w");
    int n, m, p, x, i;
    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",&p,&x);
        if(p==0)
            fprintf(f2,"%d\n",cautbin0(x));
        if(p==1)
            fprintf(f2,"%d\n",cautbin1(x));
        if(p==2)
            fprintf(f2,"%d\n",cautbin2(x));
    }
    return 0;
}