#include<stdio.h>
#include<stdlib.h>

#define NMAX 100000

int main(){
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
int v[NMAX],n,m;
int i,j,r,mij,k,gata,tip,x;
scanf("%d",&n);
for(i=0;i<n;i++) scanf("%d",&v[i]);
scanf("%d",&m);
for(k=0;k<m;k++){
	scanf("%d%d",&tip,&x);
	switch(tip){
	case 0: i=0;j=n-1;r=-1;
			while(i<=j&&r==-1){
				mij=(i+j)/2;
				if(x==v[mij]) r=mij;
				else if(x>v[mij]) i=mij+1;
					 else j=mij-1;
				}
		   //	while(r<n-1&&v[r]==x&&v[r+1]==x) r++;
			r++;
			break;
	case 1: i=0;j=n-1;gata=0;
			while(i<=j&&!gata){
				mij=(i+j)/2;
				if(x==v[mij]) {r=mij;gata=1;}
				else if(x<v[mij]) j=mij-1;
					 else i=mij+1;
				}
		   /*	if(gata)
				while(r<n-1&&v[r]==x&&v[r+1]==x) r++; */
			if(!gata)
				if(x>v[mij]) r=mij;
				else r=mij-1;
			r++;
			break;
	case 2: i=0;j=n-1;gata=0;
			while(i<=j&&!gata){
				mij=(i+j)/2;
				if(x==v[mij]) {r=mij;gata=1;}
				else if(x<v[mij]) j=mij-1;
					 else i=mij+1;
				}
			/*if(gata)
				while(r>0&&v[r]==x&&v[r-1]==x) r--;   */
			if(!gata)
				if(x<v[mij]) r=mij;
				else r=mij+1;
			r++;
			break;
	}
	printf("%d\n",r);
	}
return 0;
}