//cautare binara
#include<cstdio>
#define MAXn 100010
using namespace std;
int n,i,j,op,x,m,v[MAXn];
int binary1(int x)	//caut binar pentru prima cerinta
{
	int left=1,right=n,midd;
	while(left<=right)
		{
			midd=left+(right-left)/2;
			if(x>v[midd])
				left=midd+1;
				else
				if(x<v[midd])
					right=midd-1;
					else
					return midd;
		}
	return -1;
}
int binary2(int x)	//caut binar pentru a doua cerinta
{
	int left=1,right=n,midd,last=0;
	while(left<=right)
		{
			midd=left+(right-left)/2;
			if(v[midd]<=x)
				last=midd,left=midd+1;
				else
				right=midd-1;
		}
	return last;
}
int binary3(int x)	//caut binar pentru a treia cerinta
{
	int left=1,right=n,midd,last=0;
	while(left<=right)
		{
			midd=left+(right-left)/2;
			if(x<=v[midd])
				{
					last=midd;
					right=midd-1;
				}
				else
					left=midd+1;
		}
	return last;
}
int main ()
{
	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", &op,&x);
			if(!op)
				printf("%d\n" ,binary1(x));
				else
				if(op==1)
					printf("%d\n", binary2(x));
					else
					printf("%d\n", binary3(x));
		}
	return 0;
}