#include <stdio.h>

int cautare_binara(int vector[], int lo, int hi, int caz, int val)
{
	if (lo<=hi) {
		int med = lo + (hi-lo)/2;
		switch (caz)
		{
			case 0:
				if (val<vector[med])
				{
					return cautare_binara(vector,lo,med-1,caz,val);
				}
				else if (val>vector[med])
				{
					return cautare_binara(vector,med+1,hi,caz,val);
				}
				else {
					if (vector[med+1]==val) return cautare_binara(vector,med+1,med+1,caz,val);
					return med;
				}
				break;
			case 2:
				if (val>vector[med])
				{
					return cautare_binara(vector,med+1,hi,caz,val);
				}
				if (val<=vector[med])
				{
					if (vector[med+1]>val) return med;
					return cautare_binara(vector,lo,med-1,caz,val);
				}
				break;
			case 1:
				if (val<vector[med])
				{
					return cautare_binara(vector,lo,med-1,caz,val);
				}
				if (val>=vector[med])
				{
					if (vector[med-1]<val) return med;
					return cautare_binara(vector,med+1,hi,caz,val);
				}
				break;
		}
	}
	if (caz==2)
		return lo;
	if (caz==1)
		return hi;
	return -2;
}

int main()
{
	FILE *inptr = fopen("cautbin.in","r");
	FILE *outptr = fopen("cautbin.out","w");

	int nr = 0;
	fscanf(inptr,"%d", &nr);
	int vector[nr];
	for (int i=0;i<nr;i++)
	{
		fscanf(inptr,"%d ", &vector[i]);
	}
	int cases = 0;
	fscanf(inptr,"%d", &cases);
	int c, val;


	while (cases>0)
	{
		fscanf(inptr,"%d %d", &c, &val);
		fprintf(outptr,"%d\n", cautare_binara(vector, 0, nr-1, c, val)+1);

		cases--;
	}
	
	return 0;
}