#include<bits/stdc++.h>
using namespace std;
int m, intreb, 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;
		else dr = m - 1;
	} 
	m = (st + dr)/2;
	if (a[m] > x) m--;
	if (a[m] == x) return m;
	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", &intreb);
    for (i = 1; i <= intreb; 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;
}