#include<cstdio>
#define l 100001
using namespace std;

void citeste();
void afiseaza(int);
int cauta(int, int, int);

int a[l];
int n,m;

void citeste()
{
	int q,x,r;
	
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	
	scanf("%d",&m);
	
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&q,&x);
		
		if(!q)
		{
			r=cauta(1,n,x);
			if(r==-1) afiseaza(-1);
			else 
			{
				while(a[++r]==x);
			    afiseaza(r-1);
			}
		}
		else if(q==1)
		{
			r=cauta(1,n,x);
			while(r==-1) r=cauta(1,n,--x);
			while(a[++r]==x);
		
			afiseaza(r-1);
		}
		else
		{
			r=cauta(1,n,x);
			while(r==-1) r=cauta(1,n,++x);
			while(a[--r]==x);
			afiseaza(r+1);
		}
	}
	
	fclose(stdin);
    fclose(stdout);
}



void afiseaza(int r)
{
	printf("%d\n",r);
}



int cauta(int p,int u, int x)
{
	if(p>u) return -1;
	
	int mij=(p+u)/2;
	
	if(x==a[mij]) return mij;
	
	if(x>a[mij]) return cauta(mij+1,u,x);
	
	return cauta(p,mij-1,x);
}




int main()
{
	citeste();
	return 0;
}