#include<stdio.h>
int v[500001],n,i,x1,q,f,x;
int cb0(int li,int ls,int cheie)
{
	int m;
	while(li<=ls)
	{
		m=(li+ls)/2;
		if(v[m]<=cheie)
		 li=m+1;
		 else ls=m-1;
		 m=(li+ls)/2;
		if(v[m]>cheie) m--;
		if(v[m]==cheie) return m;
		  return -1;
	}
}
int cb1(int li,int ls,int cheie)
{
	int m,n=ls;
	while(li<ls)
	{
		m=(li+ls)/2;
		if(v[m]<=cheie)
		 li=m+1;
		else ls=m;
	}
	m=(li+ls)/2;
	if(v[m]>cheie)
	 --m;
	 return m;
}
	int cb2(int li,int ls,int cheie)
	{
		int m;
		while(li<ls)
		{
			m=(li+ls)/2;
			if(v[m]<cheie)
					  li=m+1;
					 else ls=m;
					}
					m=(li+ls)/2;
					if(v[m]>=cheie)
					m--;
					return m;
				}
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdin);
scanf("%d",&n);
for(i=1;i<=n;i++)

scanf("%d",&v[i]);
scanf("%d",&x1);
while(q!=x1)
{q++;
	scanf("%d%d",&x,&f);
	if(x==0) printf("%d\n",cb0(1,n,f));
	if(x==1) printf("%d\n",cb1(1,n,f));
	if(x==2) printf("%d\n",cb2(1,n,f));
}

}