#include<stdio.h>
int n,T,i,m,p,u,tip,x,poz,a[100011];

int main()
{	FILE *fin, *fout;
	fin = fopen ("cautbin.in", "r");
	fout = fopen ("cautbin.out", "w");
	
	fscanf (fin,"%d",&n);
	for(i=1; i<=n; ++i)
		fscanf (fin,"%d",&a[i]);
	fscanf (fin,"%d",&T);
	for(;T;--T)
	{	fscanf (fin,"%d%d",&tip,&x);
		p=1; u=n; poz=-1;
		if(tip<2)
		{	do
			{	m=(p+u)/2;
				if(a[m]==x) 
				{	poz=m; p=m+1;
					while(p<=u)
					{	m=(p+u)/2; 
						if(a[m]==x) {poz=m; p=m+1;} else u=m-1;
					}
				}
				else if(a[m]<x) p=m+1; else u=m-1;
			} while(p<=u);
			if(tip==1 && poz<0) poz=u;
			fprintf (fout,"%d\n",poz);
		}
		else
		{	do
			{	m=(p+u)/2;
				if(a[m]==x)
				{	poz=m; u=m-1;
					while(p<=u)
					{	m=(p+u)/2;
						if(a[m]==x) {poz=m; u=m-1;}
						else p=m+1;
					}
				}
				else if(a[m]<x) p=m+1; else u=m-1;
			} while(p<=u);
			if(poz<0) poz=p;
			fprintf (fout,"%d\n",poz);
		}
	}
	fclose(fout); return 0;
}