#include <stdio.h>
 
using namespace std;
int v[100001];
int cautbin0(int b,int n)
{
	int left=1,right=n,pivot=(left+right)/2;
	while(left<=right)
	{
		pivot=(left+right)/2;
		 if(v[pivot]<=b)
			left=pivot+1;
		else
			right=pivot-1;
	}
	pivot=(left+right)/2;
	if(v[pivot]>b) pivot--;
	if(b==v[pivot])
		return pivot;
	return -1;

}
int cautbin1(int b,int n)
{
	int left=1,right=n,pivot=(left+right)/2;
	n=right;
	while(left<right)
	{
		pivot=(left+right)/2;
		 if(v[pivot]<=b)
			left=pivot+1;
		else
			right=pivot;
	}
	pivot=(left+right)/2;
	if(v[pivot]>b) --pivot;
	
		return pivot;
	
}
int cautbin2(int b,int n)
{
	int left=1,right=n,pivot=(left+right)/2;
	while(left<right)
	{
		pivot=(left+right)/2;
		 if(v[pivot]<b)
			left=pivot+1;
		else
			right=pivot;
	}
	pivot=(left+right)/2;
	if(v[pivot]<b) ++pivot;
	
		return pivot;
	
}
int main()
{
	freopen(  "cautbin.in","r",stdin);
	freopen( "cautbin.out","w",stdout);
	int n,m,pivot,left,right;
	int a,b;
	scanf("%d",&n);
	for ( int i=1;i<=n;i++)
		scanf("%d",&v[i]);
	scanf("%d",&m);
	for ( int i=1;i<=m;i++)
	{
		scanf("%d %d",&a,&b);
		if(a==0)
		{b=cautbin0(b,n);
		 printf("%d\n",b);
		}
		else if (a==1)
		{
			b=cautbin0(b,n)+1;
			 printf("%d\n",cautbin1(b,n)-1);
		}
		else
		{
			b=cautbin2(b,n);
			printf("%d\n",cautbin1(b,n)+1);}


	}
}