#include <fstream>
using namespace std;

int a[100001], b[100001], primul, cautat;
int cbin(int vec[], int st, int dr, int x, int tip)
{
	long long mid=(st+dr)/2;
	if(mid>100001)
		return -1;
	if(st>dr)
	{
		if(tip==1 || tip==2)
			return primul;
		if(tip==0)
			return cautat;
	}
	if(tip==2)
	{
		if(vec[mid]<x)
		{
			return cbin(vec, mid+1, dr, x, tip);
		}
		if(vec[mid]>=x)
		{
			if(mid<primul)
				primul=mid;
			return cbin(vec, st, mid-1, x, tip);
		}
	}
	else
	{
		if(vec[mid]==x && tip==0)
		{
			if(cautat<mid)
				cautat=mid;
		}
		if(vec[mid]<=x)
		{
			if(mid>primul && tip==1)
				primul=mid;
			return cbin(vec, mid+1, dr, x, tip);
		}
		else if(vec[mid]>x)
		{
			return cbin(vec, st, mid-1, x, tip);
		}
	}
}

int main()
{
	int n, i, m, tip, el;
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	f>>n;
	for(i=1; i<=n; i++)
	{
		f>>a[i];
		b[n-i+1]=a[i];
	}
	f>>m;
	for(i=1; i<=m; i++)
	{
		cautat=-1;
		f>>tip>>el;
		if(tip==1)
			primul=-1;
		if(tip==2)
		{
			primul=100001;
			g<<cbin(a, 1, n, el, 2)<<"\n";
			continue;
		}
		g<<cbin(a, 1, n, el, tip)<<"\n";
	}
}