#include <stdio.h>
int N,v[100005];
int q0(int x)
{
	int s,d,m,i;
	for (s=1; d=N; s<=d)
	{
		m=s+(d-s)/2;
		if (v[m]>x)
			d=m-1;
		if (v[m]<x)
			s=m+1;
		if (v[m]==x)
			return m;
	}
	return -1;
}
int q1(int x)
{
	int s,d,m,i,k;
	for (s=1; d=N; s<=d)
	{
		m=s+(d-s)/2;
		if (v[m]>=x)
		{
			k=v[m];
			d=m+1;
		}
		else s=m-1;
	}
	return k;
}
int q2(int x)
{
	int s,d,m,i,k;
	for (s=1; d=N; s<=d)
	{
		m=s+(d-s)/2;
		if (v[m]<=x)
		{
			k=v[m];
			d=m+1;
		}
		else s=m-1;
	}
	return k;
}
int main()
{
	int n,i,p,x,t;
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for (i=1; i<=n; i++)
		scanf("%d",&v[i]);
	scanf("%d",&p);
	for (i=1; i<=p; i++)
	{
		scanf("%d%d",&t,&x);
		if (t==0)
			printf("%d\n",q0(x));
		if (t==1)
			printf("%d\n",q1(x));
		if (t==2)
			printf("%d\n",q2(x));
	}
}