#include <cstdio>

using namespace std;

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

	int n, qno, x, t;
	scanf("%d", &n);
	int numbers[n+1];
	for(int i=1; i<=n; ++i)
		scanf("%d", &numbers[i]);

	scanf("%d", &qno);

	for(int i=0; i<qno; ++i) {
		scanf("%d%d", &t, &x);

		int l = 1, r = n, m;

		switch (t) {
                case 0:
                while (l < r) {
                    m = (l + r) / 2;

                    if (numbers[m] > x)
                        r = m - 1;
                    else
                        l = m + 1;
                }
                m = (l+r) / 2;
				if (numbers[m] == x)
					printf("%d\n", m);
				else
                    if (numbers[m-1] == x)
                        printf("%d\n",m-1);
                    else
                        printf("-1\n");
				break;
			case 1:
			    while (l < r) {
                    m = (l + r) / 2;

                    if (numbers[m] > x)
                        r = m - 1;
                    else
                        l = m + 1;
                }
                m = (l + r) / 2;
                if (numbers[m] <= x)
                    printf("%d\n", m);
                else
                    printf("%d\n", m-1);
				break;
			case 2:
			    while (l <= r) {
                    m = (l + r) / 2;

                    if (numbers[m] >= x)
                        r = m - 1;
                    else
                        l = m + 1;
                }
                m = (l + r) / 2;
				if (numbers[m] == x)
					printf("%d\n", m);
				else
					printf("%d\n", m+1);
				break;
		}
	}
	return 0;
}