#include <stdio.h>
#include <fstream>
using namespace std;
int N,M;
int V[100005];
int Query0(int s,int f,int nr){
    int m=(s+f)/2;
    if(s==f){
        if(V[s]==nr)
            return s;
        return -1;
    }
    if(V[m]<=nr)
        return Query0(m,f,nr);
    return Query0(s,m-1,nr);
}
int Query1(int s,int f,int nr){
    int m=(s+f)/2;
    if(s>=f){
        while(V[s]>nr)
            s--;
        return s;
    }
    if(V[m]<=nr)
        return Query1(m,f,nr);
    return Query1(s,m-1,nr);
}
int Query2(int s,int f,int nr){
    int m=(s+f)/2;
    if(s>=f){
        while(V[f]<nr)
            f++;
        return f;
    }
    if(V[m]<=nr)
        return Query2(m,f,nr);
    return Query2(s,m-1,nr);
}
void Read(){
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&N);
    int i,x,nr;
    for(i=1;i<=N;i++){
        scanf("%d ",&V[i]);
    }
    scanf("%d\n",&M);
    for(i=1;i<=M;i++){
        scanf("%d %d\n",&x,&nr);
        if(x==0)
            printf("%d\n",Query0(1,N,nr));
        else if(x==1)
            printf("%d\n",Query1(1,N,nr));
        else if(x==2)
            printf("%d\n",Query2(1,N,nr));
    }
    fclose(stdout);
}
int main()
{
    Read();



    return 0;
}