#include <stdio.h>
int v[100005];
long n;
long caut(int x)
	{
	int li,ls,p=0;
	long mid;
	li=1;
	ls=n;
	mid=(li+ls)/2;
	while (li<=ls&&!p)
		{
		if (v[mid]==x) p=1;
		else
			{
			if (v[mid]>x)
				{
				ls=mid;
				mid=(li+ls)/2;
				}
			else
				{
				li=mid;
				mid=(li+ls)/2;
				}
			}
		}
	if (p) return mid;
	else return -1;
	}
int main()
{
long i,m,x,q;
int j;
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%ld",&n);
for (i=1;i<=n;i++)
	scanf("%d",&v[i]);
scanf("%ld",&m);
for (i=1;i<=m;i++)
	{
	scanf("%d %d",&q,&j);
	x=caut(j);
	if (!q)
		{
		while (v[x]==v[x+1]&&x<n)
			x++;
		printf("%ld\n",x);
		}
	else
	if (q==1)
		{
		while (v[x]<=j&&x<=n)
			x++;
		printf("%ld\n",x-1);
		}
	else
		{
		while (v[x]>=j&&x>=1)
			x--;
		printf("%ld\n",x+1);
		}
	}
return 0;
}