#include <cstdio>
#include <algorithm>

#define MAXN 100005

int a[MAXN], n, q;

using namespace std;

int main()
{
    freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);

	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	scanf("%d", &q);

	for(int i = 1; i <= q; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
        if(x == 0)
		{
		    int* ind = upper_bound(a, a + n + 1, y);
			if(a[*ind - 1] == y)
				printf("%d\n", *ind - 1);
			else 
				printf("-1\n");
		}
		if(x == 1)
		{
            printf("%d\n", *lower_bound(a, a + n, y + 1) - 1);
		}
		if(x == 2)
		{
			printf("%d\n", *upper_bound(a, a + n, y - 1) - 1);
		}
						
	}

	return 0;
}