#include<stdio.h>
int n,T,i,m,p,u,tip,x,poz,a[100001]; 
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;
}