#include <stdio.h>

int n, i, m, mode, x, mid, tmp;
int sir[100000];

int bin_search_0(int beg, int end);
int bin_search_1(int beg, int end);
int bin_search_2(int beg, int end);

int main()
{
	FILE *ifp, *ofp;

	ifp = fopen("cautbin.in", "r");
	ofp = fopen("cautbin.out", "w");

	fscanf(ifp, "%d", &n);

	for (i=0; i<n; i++)
	{
		fscanf(ifp, "%d", &sir[i]);
	}

	fscanf(ifp, "%d", &m);
	
	for (i=0; i<m; i++)
	{
		fscanf(ifp, "%d", &mode);
		fscanf(ifp, "%d", &x);
		switch (mode)
		{
		case 0:
			fprintf(ofp, "%d\n", bin_search_0(0, n-1));
			break;
		case 1:
			fprintf(ofp, "%d\n", bin_search_1(0, n-1));
			break;
		case 2:
			fprintf(ofp, "%d\n", bin_search_2(0, n-1));
			break;
		}
	}

	fclose(ifp);
	fclose(ofp);

	return 0;
}

int bin_search_0(int beg, int end)
{
	tmp=-2;
	while (beg<=end)
	{
		mid=beg+(end-beg)/2;
		if (sir[mid]>x)
		{
			end=mid-1;
		}
		else if (sir[mid]<x)
		{
			beg=mid+1;
		}
		else
		{
			tmp=mid;
			beg=mid+1;
		}
	}
	return tmp+1;
}

int bin_search_1(int beg, int end)
{
	tmp=-2;
	while (beg<=end)
	{
		mid=beg+(end-beg)/2;
		if (sir[mid]>x)
		{
			end=mid-1;
		}
		else
		{
			tmp=mid;
			beg=mid+1;
		}
	}
	return tmp+1;
}

int bin_search_2(int beg, int end)
{
	while (beg<=end)
	{
		mid=beg+(end-beg)/2;
		if (sir[mid]<x)
		{
			beg=mid+1;
		}
		else
		{
			return mid;
		}
	}
	return -1;
}