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

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

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

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

int main(){
    int x,i;
        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=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            switch(x){
                case 0: printf("%d\n",cb0(1,n));break;
                case 1: printf("%d\n",cb1(1,n));break;
                case 2: printf("%d\n",cb2(1,n));break;};
        }
}