#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int st, dr, m, v[100001], n,z,i,x,y;
int divid(int v[100001], int n, int x)
{
	int l , r , m;
	l = 0;
	r = n;
	while (l <= r)
	{
		m = (l + r) / 2;
		if (v[m] <= x)
			l = m + 1;
		else
			r = m - 1;
	}
	m = (l + r) / 2;

	if (v[m] > x) m--;
	if (v[m] == x)
		return m;
	return -1;
}
int stanga(int v[100001], int n, int x)
{
	int l, r, m;
	l = 0;
	r = n;
	while(l<r)
	{
		m = (l + r) / 2;
		if (v[m] < x)
			l = m + 1;
		else
			r = m;
	}
	return l;
}
int dreapta(int v[100001], int n, int x)
{
	int l, r, m;
	l = 0;
	r = n;
	while (l < r)
	{
		m = (l + r) / 2;
		if (v[m] <= x)
			l = m + 1;
		else
			r = m;
	}
	return l-1;
}
int main()
{
	fin >> n;
	for (i = 0; i < n; i++)
		fin >> v[i];
	fin >> m;
	for (i = 1; i <= m; i++)
	{
		fin >> y;
		fin>>x;
		if (y == 0)
			fout<< divid(v, n, x) <<endl;
		if(y == 1)
			fout << dreapta(v, n, x) +1<< endl;
		if(y == 2)
			fout << stanga(v, n, x)+1<< endl;
	}
	return 0;
}