#include <stdio.h>
#define dim 100100

int n, m, v[dim];

int caut_bin1(int x)
{
	int lo=1, hi=n, mid;
	while (lo<=hi)
	{
		mid=lo+(hi-lo)/2;
		if (x<v[mid]) hi=mid-1;
		else if (x>v[mid]) lo=mid+1;
		else return mid;
	}
	return -1;
}

int caut_bin2(int x)
{
	int lo=1, hi=n, mid, last=0;
	while (lo<=hi)
	{
		mid=lo+(hi-lo)/2;
		if (v[mid]<=x) last=mid, lo=mid+1;
		else hi=mid-1;
	}
	return last;
}

int caut_bin3(int x)
{
	int lo=1, hi=n, mid, last=n+1;
	while (lo<=hi)
	{
		mid=lo+(hi-lo)/2;
		if (v[mid]>=x) last=mid, hi=mid-1;
		else lo=mid+1;
	}
	return last;
}

int main()
{
	int i, op, x;
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	scanf("%d\n", &n);
	for (i=1; i<=n; i++) scanf("%d ", &v[i]);
	scanf("%d\n", &m);
	for (i=1; i<=m; i++)
	{
		scanf("%d %d\n", &op, &x);
		if (op==0) printf("%d\n", caut_bin1(x));
		else if (op==1) printf("%d\n", caut_bin2(x));
		else printf("%d\n", caut_bin3(x));
	}
	return 0;
}