#include<stdio.h>

int a[100010],n;
void citire(){
int i;

freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
	scanf("%d",&a[i]);
}



int c1(int val){
int m,p=1,u=n,poz=0;
	
	while(p<=u){
		m=(p+u)>>1;
		if(a[m]>val)u=m-1;
		else
		{p=m+1;
		if(a[m]==val)poz=m;}
	}
if(poz)return poz;
return -1;
}

int c2(int val){
int m,p=1,u=n,poz;
while(p<=u)
	{m=(p+u)>>1;
	if(a[m]>val)u=m-1;
	else{poz=m;p=m+1;}
	}
return poz;
}
int c3(int val){
int m,p=1,u=n,poz;
while(p<=u)
	{m=(p+u)>>1;
	if(a[m]>=val){u=m-1;poz=m;}
	else p=m+1;
	}
return poz;
}



void dist(){
int m,i,x,ok;

scanf("%d",&m);
for(i=1;i<=m;i++)
	{scanf("%d%d",&ok,&x);
	if(ok==0)
		printf("%d\n",c1(x));
	else
	if(ok==1)
		printf("%d\n",c2(x));
	else
		printf("%d\n",c3(x));
	}

}

int main(){

	citire();
	dist();
return 0;}