#include <cstdio>

int f[100005];

int main( ) {
	
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	
	int n,i,x,ld,mij,ls,a,e,m;
	scanf("%d",&n);
	for(i=1;i<=n;++i){
		scanf("%d",&f[i]);
	}
	scanf("%d",&m);
	
	
	for(e=1;e<=m;++e){
		scanf("%d %d",&a,&x);
		ls=1;ld=n;
		if(a==0){
			int k=124;
			for(;ls<=ld;) {
				mij=(ls+ld)/2;
				if(f[mij]<=x){
					ls=mij+1;
				}
				else{
					ld=mij-1;
				}
			}
			mij=(ls+ld)/2;
			if (f[mij]>x){
				--mij;
			}
			if (f[mij]==x){
				printf("%d\n",mij);
				k=0;
			}
			if(k!=0){
				printf("-1");
			}
		}
		else if(a==1){
			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);
		}
		else if(a==2){
			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;
}