#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#define N 100010
int n, v[N];
int solve0(int val)
{
	int li = 1;
	int lf = n;
	int m = (li + lf) / 2;
	while (li<=lf)
	{
		if (v[m] == val&&v[m] < v[m + 1])
			return m;
		if (v[m] <= val)
			li = m + 1;
		else
			lf = m - 1;
		m = (li + lf) / 2;
	}
	return -1;
}
int solve1(int val)
{
	int li = 1;
	int lf = n;
	int m = (li + lf) / 2;
	while (li <= lf)
	{
		if (v[m] <= val||v[m]==v[m+1])
			li = m + 1;
		else
			lf = m - 1;
		m = (li + lf) / 2;
	}
	return m;
}
int solve2(int val) 
{
	int li = 1;
	int lf = n;
	int m = (li + lf) / 2;
	while (li < lf)
	{
		if (v[m] >= val)
			lf = m - 1;
		else
			li = m + 1;
		m = (li + lf) / 2;
	}
	return m;
}
int main() 
{
	int i, m, val, tip;
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	scanf("%d", &n);
	for (i = 1; i <= n; ++i)
		scanf("%d", &v[i]);
	scanf("%d", &m);
	while (m--) 
	{
		scanf("%d%d", &tip, &val);
		if (tip == 0)
			printf("%d\n", solve0(val));
		if (tip == 1)
			printf("%d\n", solve1(val));
		if (tip == 2)
			printf("%d\n", solve2(val));
	}
	exit(0);
}