#include <stdio.h>

int n,m,a[100001];

int bins0(int p){
int lo=1,hi=n,mid;

while(lo<hi){
mid=lo+(hi-lo+1)/2;
	if(a[mid]<=p){lo=mid;}
	else{hi=mid-1;}

}

if(a[lo]==p){
	return lo;}else{return -1;}
}


int bins1(int p){
int lo=1,hi=n,mid;

while(lo<hi){
mid=lo+(hi-lo+1)/2;
	if(a[mid]<=p){lo=mid;}
	else{hi=mid-1;}

}

return lo;

}

int bins2(int p){
int lo=1,hi=n,mid;

while(lo<hi){
mid=lo+(hi-lo)/2;
	if(a[mid]>=p){hi=mid;}
	else{lo=mid+1;}

}

return lo;

}


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

scanf("%d %d",&temp1,&temp2);

if(temp1==0){
printf("%d\n",bins0(temp2));
}
else if(temp1==1){
printf("%d\n",bins1(temp2));}
else{
printf("%d\n",bins2(temp2));}

}


	return 0;}