/*
          ~Keep It Simple!~
*/
 
#include <stdio.h>
int n,v[100001];


int binarysearch0(int x)
{
	int i=1,j=n,mid;
	while(i!=j)
	{
		mid = (i+j)/2;
		if( v[mid] <= x )
			i = mid+1;
		else 
			j = mid-1;
	}
	mid = (i+j)/2;
	if( v[mid] > x ) mid--;
	if(v[mid] == x ) 
		return mid;
	return -1;
}

int binarysearch1(int x)
{
	int i=1,j=n,mid;
	while(i<=j)
	{
		mid = (i+j)/2;
		 if( v[mid]<=x )
			 i = mid+1;
		 else
			 j = mid-1;
	}
	mid = (i+j)/2;
	if(v[mid] > x) mid--;
	if(v[mid] <= x ) return mid;
	return -1;
}

int binarysearch2(int x)
{
	int i=1,j=n,mid;
	while(i<=j)
	{		
		mid = (i+j)/2;
		 if( v[mid] >= x )
			 j = mid-1;
		 else
			 i = mid+1;	
	}
	if(v[i] >= x)
	return i;
	else
		return -1;
}
int main()
{
    freopen("algsort.in","r",stdin);
	freopen("algsort.out","w",stdout);

	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&v[i]);
	int m,x,y;
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		if( x == 0 )
			printf("%d\n",binarysearch0(y));
		else if ( x == 1 )
			printf("%d\n",binarysearch1(y));
		else if ( x == 2 )
			printf("%d\n",binarysearch2(y));
	}
}