#include<stdio.h>
#define NMAX 100002
int A[NMAX];

int N;

void reading()
{
	scanf("%d",&N);

	int i;
	for(i=1; i<=N; ++i)
		scanf("%d",&A[i]);
}

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

	reading();
	
	int Q;
	scanf("%d",&Q);

	int logN;
	for( logN=1; logN<N; logN<<=1 );

	int i,j,a1,a2;

	while( Q-- )
	{
		scanf("%d%d\n",&a1,&a2);
		//printf("%d %d\n",a1,a2);

		if( !a1 )
		{
			j=logN;
			for( i=0; j; j>>=1 )
				if( i+j<N && A[ i+j ] <= a2 )
					i+=j;

			printf("%d\n",A[i]==a2?i:-1);
			continue;
		}
		if( a1==1 )
		{
			j=logN;
			for( i=0; j; j>>=1 )
				if( i+j<N && A[ i+j ] <= a2 )
					i+=j;

			printf("%d\n",i);
			continue;
		}
		if( a1==2 )
		{
			j=logN;
			for(i=N; j; j>>=1 )
				if( i-j>0 && A[ i-j ] >= a2 )
					i-=j;
			
			printf("%d\n",i);
			continue;
		}
	}

	return 0;
}