#include <fstream>

using namespace std;

long long a[100005];
long long n,m,i,x;

long long cauta(int in, long long x)
{
long long s,d,m;

if (in==0)
{

	s=0; d=n; m=(s+d)/2;
	while ((a[m]!=x)&&(s!=d))
	{
	if (x>a[m]) 
			{
			s=m+1; m=(s+d)/2;
			}
	if (x<a[m])
			{
			d=m; m=(s+d)/2;
			}
	}
	if(a[m]!=x) return(-1); 
	else
	{
	while(a[m]==x) m++;
	return(m);
	}
}

if (in==1)
{

	s=0; d=n; m=(s+d)/2;
	while ((a[m]!=x)&&(s!=d))
	{
	if (x>a[m]) 
			{
			s=m+1; m=(s+d)/2;
			}
	if (x<a[m])
			{
			d=m; m=(s+d)/2;
			}
	}
	if(a[m]!=x) return(m); 
	else
	{
	while(a[m]==x) m++;
	return(m);
	}
}
if (in==2)
{

	s=0; d=n; m=(s+d)/2;
	while ((a[m]!=x)&&(s!=d))
	{
	if (x>a[m]) 
			{
			s=m+1; m=(s+d)/2;
			}
	if (x<a[m])
			{
			d=m; m=(s+d)/2;
			}
	}
	if(a[m]!=x) return(m+1); 
	else
	{
	while(a[m]<x) m--;
	return(m+1);
	}
}

}


int main ()
{
	ifstream cin("cautbin.in");
    ofstream cout("cautbin.out");
 
    ios_base::sync_with_stdio(0);
	
	cin >> n; 
	
	for (i=0; i<n; i++) cin >> a[i];
	
	cin >> m;
	int indice;
	for (i=0; i<m; i++) 
	{
	cin >> indice >> x;
	cout << cauta(indice,x) << "\n";
	}
	
	
return 0;
}