#include <stdio.h>
int v[100005];
int q0(int x,int N)
{
	int s,d,m,i;
	
	for (s=1,d=N; s<=d;)
	{
		m=s+(d-s)/2;
		if (v[m]>x)
			d=m-1;
		if (v[m]<x)
			s=m+1;
		if (v[m]==x)
			return m;
	}
	return -1;
}
int q1(int x,int N)
{
	int s,d,m,i,k=0;
	
	for (s=1,d=N; s<=d;) 
	{
		m=s+(d-s)/2;
		if (v[m]<=x)
		{
			k=m;
			s=m+1;
		}
		else d=m-1;
	}
	return k;
}
int q2(int x,int N)
{
	int s,d,m,i,k=0;
	
	for (s=1,d=N; s<=d;)
	{
		m=s+(d-s)/2;
		if (x<=v[m])
		{
			k=m;
			d=m-1;
		}
		else s=m+1;
	}
	return k;
}
int main()
{
	int i,p,x,t,n;
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for (i=1; i<=n; i++)
		scanf("%d",&v[i]);
	scanf("%d",&p);
	for (i=1; i<=p; i++)
	{
		scanf("%d%d",&t,&x);
		if (t==0)
			printf("%d\n",q0(x,n));
		if (t==1)
			printf("%d\n",q1(x,n));
		if (t==2)
			printf("%d\n",q2(x,n));
	}
}