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

int search1(const vector<int>& v, int target, int tip)
{
	int len = v.size();
	int left = 0, right = len - 1;
	
	while(left <= right)
	{
		int mid = left + (right - left) / 2;
		
		if(v[mid] <= target)
		{
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
	}
	int ans = -1;
	
	if(left > 0 && v[left - 1] == target)
	{
		ans = left - 1;
	}
	else if(tip == 1)
	{
		ans = left;
	}
	return ans;
}

int search2(const vector<int>& v, int target)
{
	int len = v.size();
	int left = 0, right = len - 1;
	
	while(left <= right)
	{
		int mid = left + (right - left) / 2;
		
		if(v[mid] >= target)
		{
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}
	}
	if(right + 1 < len && v[right + 1] == target)
	{
		return right + 1;
	}
	return right;
}

int main()
{
	ifstream in("cautbin.in");
	ofstream out("cautbin.out");
	
	int n;
	in >> n;
	vector<int> v(n);
	
	for(int i = 0;i < n;++i)
	{
		in >> v[i];
	}
	
	int m;
	in >> m;
	
	for(int i = 0;i < m;++i)
	{
		int op, target;
		in >> op >> target;
		int ret;
		
		if(op == 0 || op == 1)
		{
			ret = search1(v, target, op);
		}
		else
		{
			ret = search2(v, target);
		}
		out<<ret<<"\n";
	}
	in.close();
	out.close();
}