#include <cstdio>

using namespace std;

int n,v[100005];

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

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

inline int CBin2(int x)
{
	int i,j,mij;
	i=1;j=n;
	while(i<j)
	{
		mij=(i+j)/2;
		if(v[mij]<x)
			i=mij+1;
		else
			j=mij;
	}
	mij=(i+j)/2;
	if(v[mij]<x)
		mij++;
	return mij;
}

int main()
{
	int i,m,nr,x;
	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", &m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d", &nr,&x);
		if(nr==0)
			printf("%d\n", CBin0(x));
		else
			if(nr==1)
				printf("%d\n", CBin1(x));
			else
				printf("%d\n", CBin2(x));
	}
	return 0;
}