#include <stdio.h>
#include <stdlib.h>
#define L 17
#define N 100000
int v[N];
int n;
int cautbin0(int x){
    int pas, r;
    pas = 1<<L;
    r=0;
    while(pas!=0){
        if( r + pas < n && v[r+pas]<=x)
            r+=pas;
        pas/=2;
    }
    if(v[r+pas] == x)
        return r+1;
    else
        return -1;
}
int cautbin1(int x){
    int pas, r;
    pas = 1<<L;
    r=0;
    while(pas!=0){
        if(r + pas < n && v[r+pas]<=x)
            r+=pas;
        pas/=2;
    }
    return r+1;
}
int cautbin2(int x){
    int pas, r;
    pas = 1<<L;
    r=0;
    while(pas!=0){
        if( r + pas < n && !(v[r+pas]>=x))
            r+=pas;
        pas/=2;
    }
    return r+2;
}
int main()
{
    FILE *f1 = fopen("cautbin.in","r"), *f2 = fopen("cautbin.out","w");

    int 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;
}