#include <stdio.h>
#define NMAX 100010
#define FILEIN "cautbin.in"
#define FILEOUT "cautbin.out"
int v[NMAX];
int N,M;
FILE *fin, *fout;
int cautbin(int T, int x)
{
	int min = 1, max = N, mid;
	if(T == 0)
	{
		while ( min <= max )
		{
			mid = (max+min)/2;
			if(v[mid] <= x)
				min = mid+1;
			else
				max = mid-1;
		}
		mid = (max+min)/2;
		if(v[mid] > x)
			mid--;
		if(v[mid] == x)
			return mid;
		return -1;
	}
	else
	if(T == 1)
	{
		while ( min < max )
		{
			mid = (max+min)/2;
			if(v[mid] <= x)
				min = mid+1;
			else
				max = mid;
		}
		mid = (max+min)/2;
		if(v[mid] > x)
			mid--;
		return mid;
	}
	else
	if(T == 2)
	{
		while ( min < max )
		{
			mid = (max+min)/2;
			if(v[mid] < x)
				min = mid+1;
			else
				max = mid;
		}
		mid = (max+min)/2;
		if(v[mid] < x)
			mid++;
		return mid;
	}
	return 0;
}

int main()
{
	fin = fopen(FILEIN, "r");
	fout = fopen(FILEOUT,"w");
	fscanf(fin, "%d", &N);
	int i,X,Y;
	for ( i = 1; i <= N; i++)
		fscanf(fin, "%d", &v[i]);
	fscanf(fin, "%d", &M);
	for ( i = 1; i <= M; i++)
	{
		fscanf(fin, "%d%d", &X, &Y);
		fprintf(fout,"%d\n",cautbin(X,Y));
	}
	fclose(fin);
	fclose(fout);
	return 0;
}