#include <stdio.h>

int a[100000];
int n,poz,x,t,tip,i;

inline int Binar(int x)
{
	int st,dr,mij,last;
	for (st=1, dr=n; st<=dr;){
		mij=(st+dr) >> 1;
		if (a[mij]<=x){
			last=mij;
			st=mij+1;
		}
		else dr=mij-1;
	}
	return last;
}

inline int Binar2(int x)
{
	int st,dr,mij,last;
	for (st=1, dr=n; st<=dr;){
		mij=(st+dr) >> 1;
		if (a[mij]>=x){
			last=mij;
			dr=mij-1;
		}
		else st=mij+1;
	}
	return last;
}

int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for (i=1; i<=n; i++)
		scanf("%d",&a[i]);
	scanf("%d",&t);
	while (t){
		t--;
		scanf("%d %d",&tip,&x);
		poz=Binar(x);
		if (tip==0){
			if (a[poz]==x) printf("%d",poz);
			else printf("-1");
		}
		if (tip==1) printf("%d",poz);
		if (tip==2){
			poz=Binar2(x);
			printf("%d",poz);
		}
		printf("\n");
	}
	fclose(stdin); fclose(stdout);
	return 0;
}