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

int a[MAX + 1], n, lgn ;

int binary_search(int val)
{
	int i, step;

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

int binary_search2(int val)
{
	int i, step;

	for (i = n, step = lgn; step; step >>= 1)
		if (i - step > 0 && 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]);
	}
	for (lgn = 1; lgn <= n; lgn <<=1)
		;
	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--;
				z++;
			} else if (a[z] > y)
				z--;
			fprintf(fout, "%d\n", z);
		} else if (x == 2)
		{
			z = binary_search2(y);
			//printf("x %d y %d z %d a[z] %d\n", x, y, z, a[z]);

			fprintf(fout, "%d\n", z);
		}
	}
	fclose(fin);
	fclose(fout);
	return 0;
}