#include<stdio.h>
#include<algorithm>
#define N_max 100001
using namespace std;
int v[N_max],n,p;
int main()
{
	int i,m,cod,x;
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	//citire vector 
	scanf("%d",&n);	for(i=1;i<=n;++i)	scanf("%d",&v[i]);
	
	scanf("%d",&m); //numar interogari
	for(i=1;i<=m;++i)
	{
		scanf("%d%d",&cod,&x);
		switch(cod)
		{
			case 0:
				p=upper_bound(v+1,v+n+1,x)-v;
				p--;
				if(v[p]==x)
					printf("%d\n",p);
				else
					printf("-1\n");
				break;
			case 1:
				p=upper_bound(v+1,v+n+1,x)-v;
				p--;
				printf("%d\n",p);
				break;
			case 2:
				p=lower_bound(v+1,v+n+1,x)-v;
				printf("%d\n",p);
				break; 
		}
	}
	return 0;
}