#include<iostream>
#include<fstream>
using namespace std;
int v[100000],m,n,x,y,i,mij;
int bin0(int l,int n0)
{
	int s;
	while(l<=n0)
	{
	s=(l+n0);
	mij=s/2;
	if(s%2==1)
	mij++;
	if(v[mij]==y)
	{
		if(v[mij+1]!=y)
		{
			return mij;
		}
		else
		{
			return bin0(mij+1,n0);
		}
	}
	else
	{
		if(v[mij]<y)
			return bin0(mij+1,n0);
		else
			if(v[mij]>y)
			return bin0(l,mij-1);
	}}
		return -1;
}
int bin1(int l,int n0)
{
	int s;
	while(l<=n0)
	{
	s=(l+n0);
	mij=s/2;
	if(s%2==1)
	mij++;
	if(v[mij]==y)
	{
		if(v[mij+1]!=y)
		{
			return mij;
		}
		else
		{
			return bin0(mij+1,n0);
		}
	}
	else
	{
		if(v[mij]<y)
			return bin0(mij+1,n0);
		else
			if(v[mij]>y)
			return bin0(l,mij-1);
	}
	
	}
		y=y+1;
		return bin1(1,n0);
}


int bin2(int l,int n0)
{
	int s;
	while(l<=n0)
	{
	s=(l+n0);
	mij=s/2;
	if(s%2==1)
	mij++;
	if(v[mij]==y)
	{
		if(v[mij-1]!=y)
		{
			return mij;
		}
		else
		{
			return bin2(1,mij-1);
		}
	}
	else
	{
		if(v[mij]<y)
			return bin2(mij+1,n0);
		else
			if(v[mij]>y)
			return bin2(l,mij-1);
	}
	
	}
		y=y-1;
		return bin2(1,n0);
}

int main()
{
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	f>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		if(x==0)
		{
		g<<bin0(1,n)<<"\n";
		}
		
		
		else
			if(x==1)
			{
			g<<bin1(1,n)<<"\n";
			}
				else
					{
					g<<bin2(1,n)<<"\n";	
					}
	}
	return 0;
}