#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=NULL, *fis2=NULL;
	fis1 = fopen_s(fis1,"cautbin.in", "r");
	fis2 = fopen_s(fis2,"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");
}