#include <cstdio>
#include <algorithm>
#define DN 100100
using namespace std;

int v[DN];

int main ()
{
    int n, m, x, y, i,t;

    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);

    for (i= 1; i <= m; ++ i)
	{
        scanf("%d %d", &t, &y);

        if (t == 0)
		{
            x = upper_bound(v + 1, v + n + 1, y) - v - 1;
            if (x <= n && x >= 1 && v[x] == y)
                printf("%d\n", x);
            else
                printf("-1\n");
        }
		else if (t == 1)
		{
            x = lower_bound(v + 1, v + n + 1, y + 1) - v - 1;
            printf("%d\n", x);
        }
		else
		{
            x = upper_bound(v + 1, v + n + 1, y - 1) - v;
            printf("%d\n", x);
        }
    }
	return 0;
}