#include<cstdio>
using namespace std;

int n,m,V[10010],i,tip,x,cautarebin0(),cautarebin1(),cautarebin2();

void read(),solve();

int main()
{
	read();
	solve();
	
	return 0;
}

void read()
{
	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);
}

void solve()
{
	for(;m;m--)
	{
		scanf("%d%d",&tip,&x);
		if(tip==0)printf("%d\n",cautarebin0());
		if(tip==1)printf("%d\n",cautarebin1());
		if(tip==2)printf("%d\n",cautarebin2());
	}
}

int cautarebin0()
{
	int st=1,dr=n,mij,sol=-1;
	while(st<=dr)
	{
		mij=st+(dr-st)/2;
		if(V[mij]==x){sol=mij;break;}
		if(V[mij]>x)dr=mij-1;
		else        st=mij+1;
	}
	if(sol==-1)return -1;
	while(V[sol+1]==V[sol])sol++;
	return sol;
}

int cautarebin1()
{
	int st=1,dr=n,mij,sol=-1;
	while(st<=dr)
	{
		mij=st+(dr-st)/2;
		if(V[mij]<=x && mij>sol){sol=mij;}
		if(V[mij]<=x)st=mij+1;
		else         dr=mij-1;
	}
	while(V[sol+1]<=x && sol+1<=n)sol++;
	return sol;
}

int cautarebin2()
{
	int st=1,dr=n,mij,sol=9999999;
	while(st<=dr)
	{
		mij=st+(dr-st)/2;
		if(V[mij]>=x && mij<sol)sol=mij;
		if(V[mij]>=x)dr=mij-1;
		else         st=mij+1;
	}
	
	while(V[sol-1]>=x)sol--;
	return sol;
}