#include <stdio.h>

int v[100001],lung,nr,p,q;

int search1(int x,int a,int b);
int search2(int x,int a,int b);
int search3(int x,int a,int b);

int main()
{
	FILE* in=fopen("cautbin.in","r");
	fscanf(in,"%d\n",&lung);
	for(int i=1;i<=lung;++i)
		fscanf(in,"%d",&v[i]);
	fscanf(in,"\n%d\n",&nr);
	FILE *out=fopen("cautbin.out","w+");
	for(int i=1;i<=nr;++i)
	{
		fscanf(in,"%d%d\n",&p,&q);
		switch(p)
		{
			case 0: fprintf(out,"%d\n",search1(q,1,lung)); break;
			case 1: fprintf(out,"%d\n",search2(q,1,lung)); break;
			case 2: fprintf(out,"%d\n",search3(q,1,lung)); break;
		}
	}
	fclose(in);
	fclose(out);
return 0;
}

int search1(int x,int a,int b)
{
	if (a==b-1)
	{
		if (v[b]==x) return b;
		else if (v[a]==x) return a;
		else return -1;
	}
	int c=(a+b)/2;
	if (x<v[c]) return search1(x,a,c);
    else return search1(x,c,b);
}
int search2(int x,int a,int b)
{
	if (a==b-1)
	{
		if (v[b]<=x) return b;
		return a;
	}
	int c=(a+b)/2;
	if (x<v[c]) search2(x,a,c);
    else search1(x,c,b);

}
int search3(int x,int a,int b)
{
	if (a==b-1)
	{
		if (v[a]>=x) return a;
		return b;
	}
	int c=(a+b)/2;
	if (x<=v[c]) search3(x,a,c);
    else search1(x,c,b);
}