#include<stdio.h>
long long v[50010],a;
int n,m,i,j,t,z;
int bs(long long a)	
	{
		int st,dr,med,last;
		st=1; dr=n;
		last=-1;
		while(st<=dr)
		{
			med=st+(dr-st)/2;
			if(v[med]<=a)
			{	
				if(v[med]==a)
					last=med;
				st=med+1;
			}
			else
				dr=med-1;
		}	
		return last;
	}	
int bs1(long long a)	
	{
		int st,dr,med,last;
		st=1; dr=n;
		last=-1;
		while(st<=dr)
		{
			med=st+(dr-st)/2;
			if(v[med]<=a)
			{	
				if(med>last)
				last=med;
				st=med+1;
			}
			else
				dr=med-1;
		}	
		return last;
	}	

int bs2(long long a)	
	{
		int st,dr,med,last;
		st=1; dr=n;
		last=100000;
		while(st<=dr)
		{
			med=st+(dr-st)/2;
			if(v[med]<a)
			{	
				st=med+1;
			}
			else
			{
				dr=med-1;
				if(last>med)
					last=med;
			}
		}	
		return last;
	}	
	
int main()
{
	int b,no,rez;
	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",&no,&b);
		if(no==0)
			rez=bs(b);
		if(no==1)
			rez=bs1(b);
		if(no==2)
			rez=bs2(b);
		printf("%d\n",rez);
		
	}
	return 0;
}