#include<stdio.h>
#include<malloc.h>
int cautareBinara1(int *vector,int stanga, int dreapta,int val,int dim)
{
	if (stanga > dreapta)
	{
		return -1;
	}
	else
	{
		int m = (stanga + dreapta) / 2;
		if (vector[m] == val)
		{
			if (m == dim - 1)
			{
				return m+1;
			}
			else
			{
				if (vector[m + 1] != val)
				{
					return m+1;
				}
				else
				{
					return cautareBinara1(vector, m + 1, dreapta, val, dim);
				}
			}
		}
		else
		{
			if (val > vector[m])
			{
				return cautareBinara1(vector, m + 1, dreapta, val, dim);
			}
			else
			{
				return cautareBinara1(vector, stanga, m - 1, val, dim);
			}
		}
 
	}
 
}
int cautareBinara2(int *vector, int stanga, int dreapta, int val, int dim)
{
	if (stanga > dreapta)
	{
		return -1;
	}
	else
	{
		int m = (stanga + dreapta) / 2;
		if (vector[m] <=val)
		{
			if (m == dim - 1)
			{
				return m + 1;
			}
			else
			{
				if (vector[m + 1]>val)
				{
					return m + 1;
				}
				else
				{
					return cautareBinara2(vector, m + 1, dreapta, val, dim);
				}
			}
		}
		else
		{
			
		return cautareBinara2(vector, stanga, m - 1, val, dim);
			
		}
 
	}
 
}
int cautareBinara3(int *vector, int stanga, int dreapta, int val, int dim)
{
	if (stanga > dreapta)
	{
		return -1;
	}
	else
	{
		int m = (stanga + dreapta) / 2;
		if (vector[m]>=val)
		{
			if (m == 0)
			{
				return m + 1;
			}
			else
			{
				if (vector[m -1]<val)
				{
					return m + 1;
				}
				else
				{
					return cautareBinara3(vector, stanga, m-1, val, dim);
				}
			}
		}
		else
		{
			
		return cautareBinara3(vector, m+1, dreapta, val, dim);
			
		}
 
	}
 
}
 
 
int main()
{
	int n,*vector,m,mutare,x;
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	scanf("%d", &n);
	vector = (int*)malloc(n * sizeof(int));
	for (int index = 0; index <n; ++index)
	{
		scanf("%d", &vector[index]);
	}
	scanf("%d", &m);
	for (int index = 0; index < m; ++index)
	{
		scanf("%d%d", &mutare,&x);
		if (mutare == 0)
		{
			printf("%d", cautareBinara1(vector, 0, n - 1, x, n));
		}
		else
		{
			if (mutare == 1)
			{
				printf("%d", cautareBinara2(vector, 0, n - 1, x, n));
			}
			else
			{
				printf("%d", cautareBinara3(vector, 0, n - 1, x, n));
			}
		}
		printf("\n");
	}

	
 
	return 0;
}