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

	}
	else
	{
		if(v[mij]<y)
			return bin1(mij+1,n0);
		else
			return bin1(l,mij-1);
	}
	
	}
if(v[mij]>y)
	y=v[mij-1];
else
	y=v[mij];
		return bin1(1,n);
}
int bin2(int l,int n0)
{
	if(l<=n0)
	{
	mij=(l+n0)/2;
	if(v[mij]==y)
	{
			while(1)
		{
		if(v[mij-1]!=y)
		{return mij;}
		mij--;
		}
	}
	else
	{
		if(v[mij]<y)
			return bin2(mij+1,n0);
		else
			return bin2(l,mij-1);
	}
	
	}
if(v[mij]<y)
	y=v[mij+1];
else
	y=v[mij];
		return bin2(1,n);
}
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;
}