#include <iostream>
#include <fstream>

using namespace std;

int v[100069];

int main()
{
	ifstream in("cautbin.in");
	ofstream out("cautbin.out");
	int N,M,x,i;
	in>>N;
	for (i=1;i<=N;i++)
		in>>v[i];
	in>>M;
	int min,max,el,med;
	for (i=1;i<=M;i++)
	{
		min=1;
		max=N;
		in>>x>>el;
		med=(min+max)/2;
		while (min<=max&&v[med]!=el)
		{
			if (el<v[med])
				max=med-1;
			else
				min=med+1;
			med=(min+max)/2;
		}
		if (x==0)
		{
			if (v[med]!=el)
				out<<-1<<"\n";
			else
			{
				while (v[med]==el)
					med++;
				med--;
				out<<med<<"\n";
			}
		}
		if (x==1)
		{
			while (v[med]<=el&&med<=N)
				med++;
			med--;
			out<<med<<"\n";
		}
		if (x==2)
		{
			while (v[med]>=el)
				med--;
			med++;
			out<<med<<"\n";
		}
	}
	return 0;
}