#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>



int binarySearch0(int v[], int l, int r,int x)
{
	if (l > r)
		return -1;
	if (l == r)
	{
		if (v[l] != x)
			return -1;
		while (v[l] == x)
			l++;
		l--;
		return l;
	}
	int m = (l + r) / 2;
	if (v[m] < x)
		return binarySearch0(v, m + 1, r, x);
	else
		return binarySearch0(v, l, m, x);
}
int binarySearch1(int v[], int l, int r, int x)
{
	if (l==r && v[l] == x)
	{
		while (l >= 1 && v[l] == x)
			l++;
		l--;
		return l;
	}
	if (l >= r)
	{
		while (l >= 1 && v[l] > x)
			l--;
		return l;
	}
	int m = (l + r) / 2;
	if (v[m] < x)
		return binarySearch1(v, m + 1, r, x);
	else
		return binarySearch1(v, l, m, x);
}
int binarySearch2(int v[], int l, int r, int x,int n)
{
	if (l >= r)
	{
		while (l <= n && v[l] < x)
			l++;
		return l;
	}
	int m = (l + r) / 2;
	if (v[m] < x)
		return binarySearch2(v, m + 1, r, x,n);
	else
		return binarySearch2(v, l, m, x,n);
}
int main()
{
	freopen("cautbin.in", "r", stdin);
	//freopen("cautbin.out", "w", stdout);

	int n,v[100010],m;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &v[i]);


	int q, x;
	scanf("%d", &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &q, &x);
		if (q == 0)
		{
			printf("%d\n", binarySearch0(v, 1, n, x));
		}
		if (q == 1)
		{
			printf("%d\n", binarySearch1(v, 1, n, x));
		}
		if (q == 2)
		{
			printf("%d\n", binarySearch2(v, 1, n, x,n));
		}
	}
}