#include <stdio.h>
#define NMAX 100000

FILE *fi = fopen("cautbin.in", "r");
FILE *fo = fopen("cautbin.out", "w");

int N, M, i, x, p;
int V[NMAX];

int cautB0(int p, int u, int x) {
	int c = (p+u)/2;

	if (u==p+1) {
		if (V[p] == x && V[p+1]!=x) return p+1;
		return -1;
	}

	if (V[c] == x) {
		if (V[c+1]!=x) return c+1;
		else return cautB0(c, u, x);
	}
	else
		if (x<V[c]) return cautB0(p, c, x);
		else return cautB0(c, u, x);
}

int cautB1(int p, int u, int x) {
	int c = (p+u)/2;

	if (u==p+1) {
		if (V[p]<x && V[u]>=x) return p+1;
		return -1;
	}

	if (V[c] == x) {
		if (V[c-1]!=x) return c;
		else return cautB1(p, c, x);
	}
	else
		if (x<V[c]) return cautB1(p, c, x);
		else return cautB1(c, u, x);
}

int cautB2(int p, int u, int x) {
	int c = (p+u)/2;

	if (u==p+1) {
		if (V[p]<=x && V[u]>x) return u+1;
		return -1;
	}

	if (V[c] == x) {
		if (V[c+1]!=x) return c+2;
		else return cautB2(c, u, x);
	}
	else
		if (x<V[c]) return cautB2(p, c, x);
		else return cautB2(c, u, x);
}

int main() {
	fscanf(fi, "%d", &N);

	for (i=0; i<N; i++) fscanf(fi, "%d", &V[i]);

	fscanf(fi, "%d", &M);
	
	for (i=0; i<M; i++) {
		fscanf(fi, "%d %d", &p, &x);
		if (p==0) fprintf(fo, "%d\n", cautB0(0, N-1, x));
		if (p==1) fprintf(fo, "%d\n", cautB1(0, N-1, x));
		if (p==2) fprintf(fo, "%d\n", cautB2(0, N-1, x));
	}

	fclose(fi);
	fclose(fo);

	return 0;
}