#include<cstdio>
using namespace std;
int v[1000001],n;
int cautare(int x,short q)
{
	int i,index=n/2;bool trigger=0;
	if(!q)
	{
		if(v[index]<=x)
			for(i=index;i<=n;i++)
			{
				if(v[i]==x)
					trigger=1;
				if(v[i]!=x&&trigger)
					return i-1;
			}
		else
			for(i=index-1;i>=1;i--)
				if(v[i]==x)
					return i;
		return -1;
	}
	if(q==1)
	{
		if(v[index]<=x)
			for(i=index;i<=n;i++)
				if(v[i]>x)
					return i-1;
		if(v[index]>x)
			for(i=index-1;i>=1;i--)
				if(v[i]<=x)
					return i;
	}
	if(q==2)
	{
		if(v[index]<x)
			for(i=index+1;i<=n;i++)
				if(v[i]>=x)
					return i;
		if(v[index]>=x)
			for(i=index;i>=1;i--)
				if(v[i]<x)
					return i+1;
	}
}
int main()
{
	freopen("cautbin.in","r",stdin);freopen("cautbin.out","w",stdout);
	int m,i,q;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
	scanf("%d",&m);
	for(;m;--m)
	{
		scanf("%d%d",&q,&i);
		printf("%d\n",cautare(i,q));
	}
}