#include<fstream>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,v[100001],m,contor,x,in,sf,mij,poz,op;
int main()
{
	//ios::sync_with_stdio(false);
	f>>n;
	for(int i=1; i<=n; i++)
		f>>v[i];
	f>>m;
	while(m--)
	{
	    f >> op >> x;
		int s = 1, d = n,m,r = -1;
		if(op == 0)
		{
			while(s <= d)
			{
				m = (s + d) / 2;
				if(v[m] == x)
					r = max(r,m);
				(v[m] <= x) ? s = m + 1 : d = m - 1;
			}
			g << r<<'\n';
		}
		if(op == 1)
		{
			while(s <= d)
			{
				m = (s + d) / 2;
				(v[m] <= x) ? r = m, s = m + 1 : d = m - 1;
			}
			g<< r << '\n';
		}
		if(op == 2)
		{
			while(s <= d)
			{
				m = (s + d) / 2;
				(v[m] >= x) ? d = m - 1, r = m : s = m + 1;
			}
			g << r << '\n';
		}
	}
	return 0;
}