#include <stdio.h>

int N, M, A[100005];

int caut0(int X){
	
	int l = 0, r = N - 1, mid;
	
	while(l + 1 < r){
		mid = (l + r) / 2;
		
		if(A[mid] == X){
			l = mid;
		}else if(A[mid] < X){
			l = mid + 1;
		}else{
			r = mid - 1;
		}
	}
	
	if(A[r] == X)
		return r;
	else if(A[l] == X) 
		return l;
	
	return -1; 
}

int caut1(int X){
	
	int l = 0, r = N - 1, mid;
	
	while(l + 1 < r){
		mid = (l + r) / 2;
		
		if(A[mid] <= X){
			l = mid;
		}else if(A[mid] > X){
			r = mid - 1;
		}
	}
	
	if(A[r] <= X)
		return r;
	else if(A[l] <= X) 
		return l;
	
	return -1; 
}

int caut2(int X){
	
	int l = 0, r = N - 1, mid;
	
	while(l + 1 < r){
		mid = (l + r) / 2;
		
		if(A[mid] >= X){
			r = mid;
		}else if(A[mid] < X){
			l = mid + 1;
		}
	}
	
	if(A[l] >= X)
		return l;
	else if(A[r] >= X) 
		return r;
	
	return -1; 
}

int main(){
	
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	
	scanf("%d", &N);
	for(int i = 0; i < N; ++i){
		scanf("%d", &A[i]);
	}
	
	for(scanf("%d", &M); M > 0; --M){
		int type, X;
		
		scanf("%d %d", &type, &X);
		
		int ans = -1;
		
		if(type == 0) ans = caut0(X) + 1;
		if(type == 1) ans = caut1(X) + 1;
		if(type == 2) ans = caut2(X) + 1;
		
		printf("%d\n", ans );
	}
	
	
return 0;	
}