#include<cstdio>
#define NMAX 100001

int v[NMAX];
int i,j,n,k,op,nr,m;

void cautare0(int x)
{
	int st=1,dr=n,mid;
	mid=st+(dr-st)/2;
	while(st<dr)
	{
		if(v[mid]<=x) st=mid+1;
		else
			dr=mid-1;
		mid=st+(dr-st)/2;
	}
	if(v[mid]>x) mid--;
	if(v[mid]!=x) printf("-1");
	else
		printf("%d\n",mid);


}

void cautare1(int x)
{
int st=1,dr=n;
int mid;
mid=st+(dr-st)/2;
while(st<dr)
{
 if(v[mid]<=x) st=mid+1;
 else
 	dr=mid-1;
 mid=st+(dr-st)/2;

}
if(v[mid]>x) mid--;
printf("%d\n",mid);

}


void cautare2(int x)
{
	int st=1,dr=n;
	int mid;
	mid=st+(dr-st)/2;
	while(st<dr)
	{
		if(v[mid]<x) st=mid+1;
		else
			dr=mid-1;
		mid=st+(dr-st)/2;
	}

if(v[mid]<x) mid++;
printf("%d\n",mid);
}

int main()
{

freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
scanf("%d",&m);
for(i=1;i<=m;i++)
{
	scanf("%d%d",&op,&nr);
	switch(op)
	{
		case 0:{cautare0(nr); break;}
		case 1:{cautare1(nr); break;}
		case 2:{cautare2(nr); break;}
	}

}
	return 0;
}