#include<stdio.h>
#define dim 100010
int n,v[dim];

int caut0(int x,int a,int b){
    if(b-a<=1){
        if(x==v[b]) return b; else
        if(x==v[a]) return a; else return -1;
    }else{
    if(v[a+(b-a)/2]<=x) caut0(x,a+(b-a)/2,b);
        else caut0(x,a,(a+b)/2);
    }
}

int caut1(int x,int a,int b){
    if(b-a<=1){
        if(x>=v[b]) return b; else
        if(x>=v[a]) return a; else return -1;
    }else{
    if(v[a+(b-a)/2]<=x) caut1(x,a+(b-a)/2,b);
        else caut1(x,a,a+(b-a)/2);
    }
}

int caut2(int x,int a,int b){
    if(b-a<=1){
        if(x<=v[b]) return b; else
        if(x<=v[a]) return a; else return -1;
    }else{
    if(v[a+(b-a)/2]<x) caut2(x,a+(b-a)/2,b);
        else caut2(x,a,a+(b-a)/2);
    }
}

int main(){
    int i,m,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);
    while(m--){
        scanf("%d",&x);
        switch(x){
            case 0: scanf("%d",&x); printf("%d\n",caut0(x,1,n)); break;
            case 1: scanf("%d",&x); printf("%d\n",caut1(x,1,n)); break;
            case 2: scanf("%d",&x); printf("%d\n",caut2(x,1,n)); break;
        }
    }
}