// cautare binara.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include <stdlib.h>

int e[100004];
int n;
int cal1(int b)
{
	int st=1,dr=n,mij;
	do
	{
		mij=st+(dr-st)/2;
		if(e[mij]==b)
			return mij;
		if(e[mij]>b)
			dr=mij;
		if(e[mij]<b)
			st=mij;
	}while(dr>st);
	return -1;
}

int cal2(int b)
{
	int st=1,dr=n,mij,rez,c1,c2;
	do
	{
		c1=st,c2=dr;
		mij=st+(dr-st)/2;
		if(e[mij]==b)
			return mij;
		if(e[mij]>b)
			dr=mij;
		if(e[mij]<b)
		{
			rez=mij;
			st=mij;
		}
		if(c1==st && c2==dr)
			break;
	}
	while(dr>st);
	return rez;
}
int cal3(int b)
{
	int st=1,dr=n,mij,rez,c1,c2;
	do
	{
		c1=st,c2=dr;
		mij=st+(dr-st)/2;
		if(e[mij]==b)
			return mij;
		if(e[mij]>b)
		{
			rez=mij;
			dr=mij;
		}
		if(e[mij]<b)
			st=mij;
		if(c1==st && c2==dr)
			break;
	}
	while(st<dr);
	return rez;
}
void decizie( FILE *f1, FILE *f2)
{
	int a,m,i,b,rez;
	fscanf(f1,"%d",&m);
	for(i=1;i<=m;i++)
	{
		fscanf(f1,"%d %d",&a,&b);
		if(a==0)
			rez=cal1(b);
		else if(a==1)
			rez=cal2(b);
		else if(a==2)
			rez=cal3(b);
		fprintf(f2,"%d\n",rez);
	}
}

int main()
{
	int i;
	FILE *f1,*f2;
	f1=fopen("cautbin.in","r");
	f2=fopen("cautbin.out","w");
	fscanf(f1,"%d",&n);
	for(i=1;i<=n;i++)
		fscanf(f1,"%d",&e[i]);
	decizie(f1,f2);
	return 0;
}