#include<stdio.h> 
int n,a[100002]; 
int cautbin0(int x) 
{     
	int i,pas=1<<16; 
	for(i=0;pas!=0;pas>>=1) 
		if(i+pas<=n && a[i+pas]<=x) 
	i+=pas; 
	if(a[i]!=x) return -1; 
	return i; 
} 
int cautbin1(int x) 
{     
	int i,pas=1<<16; 
	for(i=0;pas!=0;pas>>=1) 
		if(i+pas<=n && a[i+pas]<=x) 
	i+=pas; 
	return i; 
} 
int cautbin2(int x) 
{     
	int i,pas=1<<16; 
	for(i=0;pas!=0;pas>>=1) 
		if(i+pas<=n && a[i+pas]<x) 
	i+=pas; 
	if(i<=n-1) return i+1; 
	return i; 
} 
int main() 
{ 
	freopen("cautbin.in","r",stdin); 
	freopen("cautbin.out","w",stdout); 
	int m,i,x,y; 
	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",&x,&y); 
	if(x==0) printf("%d\n",cautbin0(y)); 
	if(x==1) printf("%d\n",cautbin1(y)); 
	if(x==2) printf("%d\n",cautbin2(y)); 
	} 
return 0; 
}#include<stdio.h> 
int n,a[100002]; 
int cautbin0(int x) 
{     
	int i,pas=1<<16; 
	for(i=0;pas!=0;pas>>=1) 
		if(i+pas<=n && a[i+pas]<=x) 
	i+=pas; 
	if(a[i]!=x) return -1; 
	return i; 
} 
int cautbin1(int x) 
{     
	int i,pas=1<<16; 
	for(i=0;pas!=0;pas>>=1) 
		if(i+pas<=n && a[i+pas]<=x) 
	i+=pas; 
	return i; 
} 
int cautbin2(int x) 
{     
	int i,pas=1<<16; 
	for(i=0;pas!=0;pas>>=1) 
		if(i+pas<=n && a[i+pas]<x) 
	i+=pas; 
	if(i<=n-1) return i+1; 
	return i; 
} 
int main() 
{ 
	freopen("cautbin.in","r",stdin); 
	freopen("cautbin.out","w",stdout); 
	int m,i,x,y; 
	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",&x,&y); 
	if(x==0) printf("%d\n",cautbin0(y)); 
	if(x==1) printf("%d\n",cautbin1(y)); 
	if(x==2) printf("%d\n",cautbin2(y)); 
	} 
return 0; 
}