#include<fstream>
using namespace std;
ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");
int n,m,a[100000];
struct q{int a,b;}x[100000];
void citire()
{
	fin>>n;
	int i;
	for( i=1;i<=n;i++)
		fin>>a[i];
	fin>>m;
	for(i=1;i<=m;i++)
		fin>>x[i].a>>x[i].b;
}
int zero(int k,int c)
{
	int mij=n/2,maxx=-1;
	int i;
	if(a[mij]<k)
	{
		int i=mij+1;
		while(i<=n)
		{
			if(a[i]==k&&c==0)
				maxx=i;
			if(a[i]<=k&&c==1)
				maxx=i;
			i++;
		}
	}
	else
		if(a[mij]>k)
		{
			i=mij-1;
			maxx=-1;
			while(maxx>=0)
			{
				if(a[i]==k&&c==0)
					maxx=i;
				if(a[i]<=k&&c==1)
					maxx=1;
				i--;
			}
		}
	else
	{
		if(k==a[mij])
			maxx=mij;
		i=mij+1;
		while(i<n)
		{
			if(a[i]==k&&c==0)
				maxx=i;
			if(a[i]<=k&&c==1)
				maxx=i;
			i++;
		}
	}
	return maxx;
}	
int trei(int k)
{
	int mij=n/2;
	int i;
	int maxx;
	maxx=-1;
	if(a[mij]>=k)
	{
		i=mij-1;maxx=mij;
		while(i>=1)
		{
			if(a[i]>=k)
				maxx=i;
			i--;
		}
	}
	else
		if(a[mij]<k)
		{
			maxx=-1;
			i=mij+1;
			while(maxx<0)
			{
				if(a[i]>=k)
					maxx=i;
				i++;
			}
		}
		return maxx;
}				
int main()
{
	citire();
	int i;
	for(i=1;i<=m;i++)
		if(x[i].a==0||x[i].a==1)
			fout<<zero(x[i].b,x[i].a)<<endl;
		else
			if(x[i].a==2)
				fout<<trei(x[i].b)<<endl;
	return 0;
}