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

unsigned int *arr;
unsigned int N, M;
unsigned int nr;
unsigned int cod;

long src0(unsigned int lo, unsigned int hi)
{
	long m;
	for(;;)
	{
		if(lo > hi) return -1;

		m = lo + (hi - lo)/2;

		if((arr[m] == nr && m < N - 1 && arr[m + 1] != nr) || 
		   (arr[m] == nr && m == N - 1))
			return m + 1;

		if(arr[m] == nr || arr[m] < nr)
		{
			lo = m + 1;
			continue;
		}

		if(arr[m] > nr)
		{
			hi = m - 1;
			continue;
		}
	}
}

long src1(unsigned int lo, unsigned int hi)
{
	long m;
	for(;;)
	{
		m = lo + (hi - lo)/2;

		if((arr[m] <= nr && m < N - 1 && arr[m + 1] > nr) ||
		   (arr[m] <= nr && m == N - 1))
			return m + 1;

		if(arr[m] <= nr)
		{
			lo = m + 1;
			continue;
		}

		if(arr[m] > nr)
		{
			hi = m - 1;
			continue;
		}
	}
}

long src2(unsigned int lo, unsigned int hi)
{
	long m;
	for(;;)
	{
		m = lo + (hi - lo)/2;

		if((arr[m] >= nr && m > 0 && arr[m - 1] < nr) ||
		   (arr[m] >= nr && m == 0))
			return m + 1;

		if(arr[m] >= nr)
		{
			hi = m - 1;
			continue;
		}

		if(arr[m] < nr)
		{
			lo = m + 1;
			continue;
		}
	}
}

int main()
{
	FILE *fpi = fopen("cautbin.in", "r");
	FILE *fpo = fopen("cautbin.out", "w");
	unsigned int i;

	fscanf(fpi, "%u", &N);
	arr = (unsigned int*)malloc(sizeof(unsigned int) * N);
	for(i = 0; i < N; ++i)
		fscanf(fpi, "%u", arr + i);

	fscanf(fpi, "%u", &M);
	for(i = 0; i < M; ++i)
	{
		fscanf(fpi, "%u", &cod);
		fscanf(fpi, "%u", &nr);

		switch(cod)
		{
		case 0:
			fprintf(fpo, "%d\n", src0(0, N - 1));
			break;
		case 1:
			fprintf(fpo, "%d\n", src1(0, N - 1));
			break;
		case 2:
			fprintf(fpo, "%d\n", src2(0, N - 1));
			break;
		}
	}

	fclose(fpo); fclose(fpi);
	free(arr);

	return 0;
}