#include<fstream>
using namespace std;

#define MAX 100010

int N,M,v[MAX];


ifstream in("cautbin.in");
ofstream out("cautbin.out");

int inline max(int e1,int e2)
{
	if(e1>e2)
		return e1;
	return e2;
}
int inline min(int e1,int e2)
{
	if(e1<e2)
		return e1;
	return e2;
}

void operatie(int op,int el)
{
	int st=1,ul=N,mid,m=-1;
	if(op==0)
	{
		while(st<=ul)
		{
			mid=(ul+st)/2;
			if(v[mid]==el)
			{
				m=max(mid,m);
				st=mid+1;
			}
			else if(v[mid]<el)
			  st=mid+1;
			else
			  ul=mid-1;
		}
		out<<m<<'\n';
	}

	else if(op==1)
	{
		while(st<=ul)
		{
			mid=(ul+st)/2;
			if(v[mid]<=el)
			{
				m=max(mid,m);
				st=mid+1;
			}
			else
			  ul=mid-1;
		}
		out<<m<<'\n';
	}
	else if(op==2)
	{
		m=(1<<30);
		while(st<=ul)
		{
         	mid=(ul+st)/2;
			if(v[mid]>=el)
			{
				m=min(mid,m);
				ul=mid-1;
			}
			else
			  st=mid+1;
		
	    }
		out<<m<<'\n';
	}
}

int main()
{
	in>>N;
	for(int i=1;i<=N;i++)
		in>>v[i];

	in>>M;
	int op,nr;
	for(int i=1;i<=M;i++)
	{
		in>>op>>nr;
		operatie(op,nr);
	}
	in.close();
	out.close();
	return 0;
}