#include <cstdio>

using namespace std;
int n,v[100003],cerinta,x,m,k,prima,ultima;
int cb0 ()
{
	prima=1;ultima=n;
	while(prima<=ultima)
	{
		k=(prima+ultima)/2;
		if(v[k]==x && (k==n || v[k+1]>x))
			return k;
		else if(v[k]<=x)
			prima=k+1;
		else if (v[k]>x)
			ultima=k-1;
	}
	return -1;
}
int cb1 ()
{
	prima=1;ultima=n;
	while(prima<=ultima)
	{
		k=(prima+ultima)/2;
		if(v[k]<=x && (k==n || v[k+1]>x))
			return k;
		else if (v[k]<=x)
			prima=k+1;
		else if(v[k]>x)
			ultima=k-1;
	}
}
int cb2 ()
{
	prima=1;ultima=n;
	while(prima<=ultima)
	{
		k=(prima+ultima)/2;
		if(v[k]>=x && (k==1 || v[k-1]<x))
			return k;
		else if (v[k]>=x)
			ultima=k-1;
		else if(v[k]<x)
			prima=k+1;
	}
}
int main ()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	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", &cerinta, &x);
		if(cerinta==0)
			printf("%d\n", cb0());
		else if (cerinta==1)
			printf("%d\n", cb1());
		else
			printf("%d\n", cb2());
	}
	return 0;
}