#include<stdio.h>
int N,M;
int a[100002];
int bs0(int x)
	{
		int st,dr,med,last=-1;
			st=1;
			dr=N;
			while(st<=dr)
				{
					med=(st+dr)/2;
					if(x>=a[med])
						{
							last=med;
							st=med+1;
						}
					else
						dr=med-1;
				}
				return last;
	}
int bs1(int x)
	{
		int st,dr,med,last=-1;
			st=1;
			dr=N;
			while(st<=dr)
				{
					med=(st+dr)/2;
					if(x>=a[med])
						{
							last=med;
							st=med+1;
						}
					else
						dr=med-1;
				}
				return last;
	}
int main()
{
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
int i,poz;
scanf("%d",&N);
for(i=1;I<=N;i++)
	scanf("%d",&a[i]);
scanf("%d",&M);
for(i=1;i<=M;i++)
	{
		scanf("%d%d",&tip,&x);
		if(tip==0)
			{
			poz=bs0(x);
			if(a[poz]!=x)
				printf("-1\n");
			else
				printf("%d\n",poz);
			}
		else
			if(tip==1)
				{
					poz=bs0(x);
					printf("%d\n",poz);
				}
			else
				{
					poz=bs1(x);
					printf("%d\n",poz);
			}
	}
return 0;
}