#include<fstream>
#define dmax 100003
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");

int n, m, x[dmax];


int bins(int q, int k)
{
	int l, r, m;
	
	l = 1;
	r = n;
	
	while(l <= r)
	{
		m = l + (r-l)/2;

		if(x[m] == k)
		{	
			l = r+1;
			while(x[m+1] == k)
				m++;
		}	

		else if(x[m] < k)
			l = m+1;
		else r = m-1;
	}

	if(q == 0)
	{	
		if(x[m] == k)
			return m;	
		return -1;
	}	

	if(q == 1)
	{	
		m--;
		while(x[m+1] <= k && m<n)
			m++;
		return m;
	}	
		
	else
	{	
		while(x[m-1] >= k && m>1)
			m--;	
		return m;
	}	
}
int main()
{
	in>>n;
	
	for(int i=1; i<=n; i++)
		in>>x[i];
	
	in>>m;
	
	for(int i = 0; i<m; i++)
	{
		int q, k;
		
		in>>q>>k;
		
		out<<bins(q, k)<<'\n';
	}

	in.close();
	out.close();

	return 0;
}