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

void caut1()
{	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;
}

void caut2()
{	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;
}

void rez()
{	scanf ("%d",&n);
	for(i=1; i<=n; ++i) scanf ("%d",&a[i]);
	scanf ("%d",&T);
	for(;T;--T)
	{	scanf ("%d%d",&tip,&x);
		p=1; u=n; poz=-1;
		if(tip<2) caut1();
		else caut2();
		printf ("%d\n",poz);
	}
}

int main()
{	freopen ("cautbin.in", "r", stdin);
	freopen ("cautbin.out", "w", stdout);

	rez();
	return 0;
}