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

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

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

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

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