#include <fstream>
using namespace std;

int a[100005],n,m,i,x,op;

int cautbin0 (int l, int r)
{
	if (l<=r)
	{
		int m = (l+r)/2;
		if (a[m] <= x) cautbin0 (m,r);
		if (a[m] > x) cautbin0 (l,m);
	}
	m = (l + r)/2;
	if (a[m] > x) m --;
	if (a[m] == x) return m;
	return -1;
}

int cautbin1 (int l, int r)
{
	if (l<=r)
	{
		int m = (l+r)/2;
		if (a[m] <= x) cautbin0 (m,r);
		if (a[m] > x) cautbin0 (l,m);
	}
	m = (l + r)/2;
	if (a[m]>x) m--;
	return m;
}

int cautbin2 (int l, int r)
{
	if (l<=r)
	{
		int m = (l+r)/2;
		if (a[m] <= x) cautbin0 (m,r);
		if (a[m] > x) cautbin0 (l,m);
	}
	m = (l + r)/2;
	if ( a[m]<x) m++;
	return m;
}

int main ()
{
	ifstream f ("cautbin.in");
	ofstream g ("cautbin.out");
	f >>n;
	for (i=1; i<=n; i++)
		f >>a[i];
	f >>m;
	for (i=1; i<=m; i++)
	{
		f >> op >> x;
		if (op==0) g <<cautbin0 (1,n);
		if (op==1) g <<cautbin1 (1,n);
		if (op==2) g <<cautbin2 (1,n);
	}
	return 0; 
}