#include <stdio.h>
int f[10005];

int cautbin0(int ls, int ld, int x) {
    
	int mij;

    for(;ls<=ld;){
        mij=(ls+ld)/2;
        if (f[mij]<=x){
            ls=mij+1;
		}
        else{
            ld=mij-1;
		}
    }
    mij=(ld+ls)/2;
    if (f[mij]>x){ 
		--mij;
	}
    if (f[mij] == x){
        printf("%d\n",mij);
		return 0;
	}
    printf("-1\n");
	return 0;
}

int cautbin1(int ls, int ld, int x) {
    
	int mij;

    for(;ls<ld;){
        mij=(ls+ld)/2;
        if(f[mij]<=x){
            ls=mij+1;
		}
        else{
            ld=mij;
		}
    }

    mij=(ls+ld)/2;
    if(f[mij]>x){
       --mij;
	}
    printf("%d\n",mij);
	return 0;
}

int cautbin2(int ls, int ld, int x) {
   
	int mij;

    for(;ls<ld;){
        mij=(ls+ld)/2;
        if (f[x]<x){
            ls=mij+1;
		}
        else{
            ld=mij;
		}
    }
    
    mij=(ls+ld)/2;
    if(f[mij]<x){
       ++mij;
	}
    printf("%d\n",mij);
	return 0;
}

int main () {
    int i, n, m, a, x;

    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d ", &n);
    for (i=1;i<=n;++i){
        scanf("%d ",&f[i]);
	}
    
    scanf("%d",&m);

    for(i=1;i<=m;++i){
		scanf("%d %d", &a, &x);
		if (a==0){
			cautbin0(1, n, x);
		}
		if (a==1){
			cautbin1(1, n, x);
		}
		if (a==2){
			cautbin2(1, n, x);
		}
    }
	return 0;
}