#include <stdio.h>

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

	int N, M, info, x, i;
	int a[100001];
	int start, end, mid;

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

	scanf("%d ", &M);
	for(i=0; i<M; i++){
		scanf("%d %d ", &info, &x);
		start = 1;
		end = N;
		if (info == 0){
			while (start < end){
				mid = (start + end ) / 2;
				if(a[mid] <= x)
					start = mid + 1;
				else 
					end = mid - 1;
			}
			mid = (start + end ) / 2;
			if( a[mid] > x) mid --;
			if( a[mid] == x)
				printf("%d\n", mid);
			else
				printf("-1\n");
		} else if (info == 1){
			while (start < end){
				mid = (start + end) / 2;
				if (a[mid] <= x)
					start = mid +1;
				else
					end = mid;
			}
			mid = (start + end) / 2;
			if (a[mid] > x)
				mid --;
			printf("%d\n", mid);
		} else {
			while (start < end){
				mid = (start + end) / 2;
				if (a[mid] < x)
					start = mid + 1;
				else 
					end = mid;
			}
			mid = (start + end) / 2;
			if (a[mid] < x)
				mid ++;
			printf("%d\n", mid);
		}
	}

	return 0;
}