#include <cstdio>
#define DIM 100005
int v[DIM], n, m;

int cautbin(int t, int x, int st, int dr)
{
	
	if (t == 0)
	{
		if (st >= dr)
		{
			if (v[dr] == x)
				return dr;
			
			if (v[dr - 1] == x)
				return dr -1;
				
			if (v[dr + 1] == x)
				return dr + 1;
			
			
			return -1;
		}
		
		int m = st + (dr - st) / 2;
		if (v[m] <= x)
			return cautbin(t, x, m + 1, dr);
		
		else
			return cautbin(t, x, st, m - 1);
		
	}
	
	if (t == 1)
	{
		if (st >= dr)
		{
			if (v[dr - 1] == x)
				return dr - 1;
			
			return dr;
			
			 
		}
		int m = st + (dr - st)/2;
		if (v[m] <= x)
			return cautbin(t, x, m + 1, dr);
		else
			return cautbin(t, x, st, m - 1);
	}
	
	if (t == 2)
	{
		if (st >= dr)
		{
			if (v[st] < x)
				return st + 1;
			
			return st;
			
		}
		int m = st + (dr - st)/2;
		if (v[m] < x)
			return cautbin(t, x, m + 1, dr);
		else
			return cautbin(t, x, st, m - 1);
	}
	
	return -2;
}

int main()
{
	FILE *f = fopen("cautbin.in", "r");
	fscanf(f, "%d", &n);
	int i;
	for (i = 1; i <= n; ++i)
		fscanf(f, "%d", &v[i]);
	
	int type, x;
	FILE *g = fopen("cautbin.out", "w");
	fscanf(f,"%d", &m);
	for (i = 1; i <= m; ++i)
	{
		fscanf(f, "%d%d", &type, &x);
		fprintf(g, "%d\n", cautbin(type, x, 1, n));
		
	}
	
	fclose(f);
	fclose(g);
	return 0;
	
}