#include<bits/stdc++.h>
using namespace std;
int m, n, p, q, i, x1, a[100005], st, dr, z;
int unu(int x)
{
	while (st <= dr) 
	{
		m = (st + dr)/2;
		if (a[m] <= x) st = m + 1;
		if (a[m] > x) dr = m - 1;
	} 
	m = (st + dr)/2;
	if (a[m] > x) m--;
	if (a[m] == x) return m;
	else  return -1;
}

int doi(int x)
{
	while (st < dr)
	{ 
	    m = (st + dr)/2;
	    if (a[m] <= x) st = m+1;
	    else dr = m;
	}
    m = (st + dr)/2;
    if (a[m] > x) --m;
    return m;
}
int trei(int x)
{
	while (st < dr)
	{
		m = (st + dr)/2;
		if (a[m] >= x) dr = m;
		if (a[m] < x) st = m + 1; 
	}
	m = (st + dr)/2;
	if (a[m] < x) m ++;
	return m;
}
int main()
{
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	scanf("%d", &n);
	for (i = 1; i <= n; i++) scanf("%d", &a[i]);
	scanf("%d", &m);
	for (i = 1; i <= m; i++) 
	{
	scanf("%d %d", &q, &x1);
	st = 1;
	dr = n;
	if (q == 0) z = unu(x1);
	if (q == 1) z = doi(x1);
	if (q == 2) z = trei(x1);
	printf("%d\n", z);
	}
	return 0;
}