#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
	unsigned int v[100000],n,m,t,nr,poz;
	unsigned int *p;
	FILE *f=fopen("cautbin.in","r"),*g=fopen("cautbin.out","w");
	fscanf(f,"%u\n",&n);
	for(int i=0;i<n;i++)
		fscanf(f,"%u",&v[i]);
	fscanf(f,"%u",&m);
	for(int i=0;i<m;i++)
	{
		fscanf(f,"%u %u\n",&t,&nr);
		if(t<2)
		{
			p=upper_bound(v,v+n,nr);
			poz=p-v;
			if(poz!=n)
				fprintf(g,"%u\n",poz);
			else
				fprintf(g,"0\n");
		}
		else
		{
			p=lower_bound(v,v+n,nr);
			poz=p-v+1;
			if(poz-1!=n)
				fprintf(g,"%u\n",poz);
			else
				fprintf(g,"0\n");
		}
	}
	return 0;
}