#include<stdio.h>

const int N = 1<<17;//2 la puterea 17

int n,v[N];

void citire()
{
	int i;
	scanf("%d",&n);
	for(i=1 ; i<=n ; ++i)
		scanf("%d",&v[i]);
}

int caut0(int x)
{
	int st=1,dr=n,m;//intervalul in care-l caut pe x este [st,dr]; la primul pas caut in tot vectorul
	while(st!=dr)//cat timp intervalul in care caut contine mai mult de un element
	{
		m=(st+dr+1)/2;//m=pozitia din mijlocul intervalului
		if(x>=v[m])
			st=m;
		else
			dr=m-1;
	}
	if(v[st]==x)
		return st;
	return -1;
}

int caut1(int x)
{
	int st=1,dr=n,m;//intervalul in care-l caut pe x este [st,dr]; la primul pas caut in tot vectorul
	while(st!=dr)//cat timp intervalul in care caut contine mai mult de un element
	{
		m=(st+dr+1)/2;//m=pozitia din mijlocul intervalului
		if(x>=v[m])
			st=m;
		else
			dr=m-1;
	}
	return st;
}

int caut2(int x)
{
	int st=1,dr=n,m;//intervalul in care-l caut pe x este [st,dr]; la primul pas caut in tot vectorul
	while(st!=dr)//cat timp intervalul in care caut contine mai mult de un element
	{
		m=(st+dr)/2;//m=pozitia din mijlocul intervalului
		if(x<=v[m])
			dr=m;
		else
			st=m+1;
	}
	if(v[st]<x)
		return st+1;
	return st;
}

int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	citire();
	int m,tip,x;
	scanf("%d",&m);
	while(m--)
	{
		scanf("%d%d",&tip,&x);
		if(tip==0)
			printf("%d\n",caut0(x));
		if(tip==1)
			printf("%d\n",caut1(x));
		if(tip==2)
			printf("%d\n",caut2(x));
	}
	return 0;
}