#include <fcntl.h>
#include <stdio.h>
#include <unistd.h>
#include <math.h>

#define MAX 100000
int v[MAX], n, f;

int cautare(int i, int j, int nr)
{
	int ind = (i+j) / 2;
	if (i >= j) return ind;
	else if (v[ind] == nr) return ind;
	else if (v[ind] < nr) return cautare(ind+1, j, nr);
	else return cautare(i, ind-1, nr);
}

int main()
{
	int i, m, t, nr, p;
	FILE* in = fopen("cautbin.in", "r");
	FILE* out = fopen("cautbin.out", "w");
	
	fscanf(in, "%d", &n);
	for (i = 0; i<n; i++)
		fscanf(in, "%d", &v[i]);
	fscanf(in, "%d", &m);
	for (i = 0; i<m; i++)
	{
		fscanf(in, "%d %d", &t, &nr);
		
		p = cautare(0, n-1, nr);
		
		
		switch (t)
		{
			case 0:
				if ( v[p] != nr ) p = -2;
				else
					while (v[p+1] == nr)
						p++;
				break;
			case 2:
				if (p < n-1) 
				{ 
					while (v[p+1] == nr)
						p++;
					if (v[p] < nr) p++;
				}
				break;
			case 1:
				if (p > 0)
				{ 
					while (v[p-1] == nr)
							p--;
					if (v[p] > nr) p--;
				}
				break;
		}
		
		//fprintf(out, "%d %d %d\n", nr, v[p], p+1);
		fprintf(out, "%d\n", p+1);
	}
	fclose(in); fclose(out);
	
	return 0;
}