#include <stdio.h>
int n,m,v[100001],y;

int caut_bin_0(int lf,int rt){
    if(lf==rt){
        if(rt>n)return -1; else return rt; } else {
    int md=(lf+rt)/2;
        if(v[md]>y)return caut_bin_0(lf,md-1);else
            return caut_bin_0(md,rt); };
}

int caut_bin_1(int lf,int rt){
    if(lf==rt)return rt;else {
    int md=(lf+rt)/2;
        if(v[md]>y)return caut_bin_1(lf,md-1); else
            return caut_bin_1(md,rt); };
}

int caut_bin_2(int lf,int rt){
    if(lf==rt)return rt;else {
    int md=(lf+rt)/2;
        if(v[md]<y)return caut_bin_2(md+1,rt); else
            return caut_bin_2(lf,md); };
}

int main(){
    int i,x;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
        scanf("%d",&n);
        for(i=1;i<=n;i++)scanf("%d",&v[i]);
        scanf("%d",&m);
        for(i=0;i<m;i++){
            scanf("%d%d",&x,&y);
            if(x==0)printf("%d\n",caut_bin_0(1,n+1)); else
            if(x==1)printf("%d\n",caut_bin_1(1,n+1)); else
            if(x==2)printf("%d\n",caut_bin_2(1,n+1));};
}