# include <fstream>
	using namespace std;
	
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	
	int t,n,q,k,x;
	int v[100009];
	int p,u,m;
	
	
	int cb0(int p, int u, int ans)  //caz0
	{	
		int m;
		while (p <= u)
		{	m = (p + u) / 2;
			if(v[m] <= ans) p = m + 1;
			else u = m - 1;
		}
		
		m = (p + u) / 2;
		
		if(v[m] > ans) --m;
		if(v[m] == ans) return m;
		return -1;
	}
	
	
	int cb1(int p, int u, int ans)  //caz1
	{	
		int m; n = u;
		while(p < u)
		{	m = (p + u) / 2;
			if(v[m] <= ans) p = m + 1;
			else u = m;
		}
		
		m = (p + u) / 2;
		
		if(v[m] > ans) return m-1;
		return m;
	}
	
	
	int cb2(int p, int u, int ans)  //caz2
	{	
		int m;
		while(p < u)
		{	m = (p + u) / 2;
			if(v[m] < ans) p = m + 1;
			else u = m;
		}
		
		m = (p + u) / 2;
		
		if(v[m] < ans) ++m;
		return m;
	}
	
	int main()
	{
		f>>n;
		for(int i=1; i<=n; ++i) 
			f>>v[i];
		f>>t;
		while(t)
		{	f>>k>>x;
			if(k==0) g<<cb0(1,n,x)<<'\n';
			if(k==1) g<<cb1(1,n,x)<<'\n';
			if(k==2) g<<cb2(1,n,x)<<'\n';
			t--;
		}
		
		return 0;
	}