#include <stdio.h>
#include <stdlib.h>
#define MAX 100001
#define in "cautbin.in"
#define out "cautbin.out"

int a[MAX + 1], n ;

int binary_search(int val)
{
	int i, step;
	
	for (step = 1; step <= n; step <<=1)
		;
		
	for (i = 0; step; step >>= 1)
		if (i + step <= n && a[i+step] <= val)
			i += step;	
	return i;
}


int main()
{
	int i, z, m, x, y;
	FILE *fin, *fout;
	
	if ((fin = fopen(in, "r")) == NULL)
	{
		printf("Eroare \n");
		exit(-1);
	}
	//read dimension of vectors
	fscanf(fin, "%d", &n);

	//read the vectors
	for (i = 1; i<=n ; i++)
	{
		fscanf(fin, "%d", &a[i]);
	}
	fscanf(fin, "%d", &m);
	fout = fopen(out, "w");
/*	for (i = 0; i <= n; i++)
		printf("%d ", a[i]);		
	printf("\n");*/
	for (i = 0; i < m; i++)
	{
		fscanf(fin, "%d%d", &x, &y);
		if (x == 0)
		{
			z = binary_search(y);
			//printf("x %d y %d z %d a[z] %d\n", x, y, z, a[z]);
			fprintf(fout, "%d\n", a[z] == y ? z : -1);
		}
		else if (x == 1)
		{
			z = binary_search(y);
			//printf("x %d y %d z %d a[z] %d\n", x, y, z, a[z]);
			if (a[z] == y)
			{
				while (a[z] == y)
					z--;
				z++;
			}
			fprintf(fout, "%d\n", z);
		} else if (x == 2)
		{
			z = binary_search(y);
			//printf("x %d y %d z %d a[z] %d\n", x, y, z, a[z]);
			if (a[z] == y)
			{
				while (a[z] == y)
					z++;
				z--;
			}
			else if (a[z] < y)
				z++;
			fprintf(fout, "%d\n", z);
		}
	}
	fclose(fin);
	fclose(fout);
	return 0;
}