#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

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

int a[100001];
int n;
int m;

int main()
{
	fin >> n;
	for(int i = 1; i <= n; ++i)
		fin >> a[i];
	
	fin >> m;
	int x, y;
	for(int i = 1; i <= m; ++i)
	{
		fin >> x >> y;
		if( x == 0)
		{
			if( binary_search(a+1, a+n+1, y) == false)
				fout << -1 << '\n';
			else
				fout << upper_bound(a+1, a+n+1, y) - a - 1 << '\n';;
		}	
		if( x == 1)
		    fout << lower_bound(a+1, a+n+1, y+1) - a - 1 << '\n';;
		
		if(x == 2)
			fout << upper_bound(a+1, a+n+1, y-1) - a << '\n';;
	}

return 0;
}