#include "stdio.h"

FILE *f, *g;
int N, M;
int a[100001];
int type, x;

int cautare_binara_0(int low, int high, int x)
{
	if(low == high)
	{
		if(a[low] == x)
			return low;
		else
			return -1;
	}
	else if(low + 1 == high)
	{
		if(a[high] == x)
			return high;
		else if(a[low] == x)
			return low;
		else 
			return -1;
	}

	int mid = low + (high-low) / 2;
	
	if(x >= a[mid])
		return cautare_binara_0(mid, high, x);
	else
		return cautare_binara_0(low, mid, x);
}

int cautare_binara_1(int low, int high, int x)
{
	if(low == high)
	{
		if(a[low] <= x)
			return low;
		else
			return -1;
	}
	else if(low + 1 == high)
	{
		if(a[high] <= x)
			return high;
		else if(a[low] <= x)
			return low;
		else 
			return -1;
	}

	int mid = low + (high-low) / 2;
	
	if(x <= a[mid])
		return cautare_binara_1(mid, high, x);
	else
		return cautare_binara_1(low, mid, x);
}

int cautare_binara_2(int low, int high, int x)
{
	if(low == high)
	{
		if(a[low] >= x)
			return low;
		else
			return -1;
	}
	else if(low + 1 == high)
	{
		if(a[low] >= x)
			return low;
		else if(a[high] >= x)
			return high;
		else 
			return -1;
	}

	int mid = low + (high-low) / 2;
	
	if(x <= a[mid])
		return cautare_binara_2(low, mid, x);
	else
		return cautare_binara_2(mid, high, x);
}

int main()
{
	f = fopen("cautbin.in", "r");
	g = fopen("cautbin.out", "w");

	fscanf(f, "%d", &N);
	for(int i = 1; i <= N; i++)
		fscanf(f, "%d", &a[i]);

	for(int i = 1; i < N; i++)
		for(int j = i+1; j <= N; j++)
		{
			if(a[i] > a[j])
			{
				int aux = a[i];
				a[i] = a[j];
				a[j] = aux;
			}
		}

	fscanf(f, "%d", &M);
	for(int i = 0; i < M; i++)
	{
		fscanf(f, "%d", &type);
		fscanf(f, "%d", &x);
		if(type == 0)
			fprintf(g, "%d\n", cautare_binara_0(1, N, x));
		else if(type == 1)
			fprintf(g, "%d\n", cautare_binara_1(1, N, x));
		else if(type == 2)
			fprintf(g, "%d\n", cautare_binara_2(1, N, x));	
	}

	fclose(f);
	fclose(g);

	return 0;
}