#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,*fis1,*fis2;
	fis1 = fopen("cautbin.in", "r");
	fis2 = fopen("cautbin.out", "w");

	fscanf(fis1,"%d", &n);
	vector = (int*)malloc(n * sizeof(int));
	for (int index = 0; index <n; ++index)
	{
		fscanf(fis1,"%d", vector[index]);
	}
	fscanf(fis1, "%d", &m);
	for (int index = 0; index < m; ++index)
	{
		fscanf(fis1, "%d%d",&mutare,&x);
		if (mutare == 0)
		{
			fprintf (fis2,"%d", cautareBinara1(vector, 0, n - 1, x, n));
		}
		else
		{
			if (mutare == 1)
			{
				fprintf(fis2, "%d", cautareBinara2(vector, 0, n - 1, x, n));
			}
			else
			{
				fprintf(fis2, "%d", cautareBinara3(vector, 0, n - 1, x, n));
			}
		}
		fprintf(fis2, "\n");
	}
	fclose(fis1);
	fclose(fis2);
	

	system("pause");
}