//#include "stdafx.h"
#include <stdio.h>

const int maxn = 100333;

int n, m;
int values[maxn];

int caut_bin(int op, int x)
{
	int left = 0, right = n - 1, res = -1;
	while (left <= right)
	{
		int mid = left + (right - left) / 2;
		
		if (op == 0)
		{
			if (values[mid] <= x)
			{
				if (values[mid] == x) 
					res = mid + 1;
				left = mid + 1;
			}				
			else if (values[mid] > x)
				right = mid - 1;
		}
		else if (op == 1)
		{
			if (values[mid] <= x)
			{
				res = mid + 1;
				left = mid + 1;
			}
			if (values[mid] > x)
				right = mid - 1;
		}
		else if (op == 2)
		{
			if (values[mid] < x)
				left = mid + 1;
			if (values[mid] >= x)
			{
				res = mid + 1;
				right = mid - 1;
			}
		}
	}

	return res;
}

int main()
{
	int i, j, op, x;
	FILE *fin = fopen("cautbin.in", "rt"), *fout = fopen("cautbin.out", "wt");

	fscanf(fin, "%d", &n);
	for (i=0; i<n; i++)
		fscanf(fin, "%d", &values[i]);
	fscanf(fin, "%d", &m);
	for (i=0; i<m; i++)
	{
		fscanf(fin, "%d %d", &op, &x);
		int res = caut_bin(op, x);
		fprintf(fout, "%d\n", res);
	}


	fclose(fin), fclose(fout);
}