#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;



int main(){
	
	vector<int>a;
	int n,x,op;
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&x);a.push_back(x);
	}
	
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&op);
		scanf("%d",&x);
		if(op==0){
			vector<int>::iterator it=upper_bound(a.begin(),a.end(),x);
			it--;
			if((*it)!=x) printf("-1\n");
				else
				printf("%d\n",it-a.begin()+1); 
		}
		else
		if(op==1){
			vector<int>::iterator it=upper_bound(a.begin(),a.end(),x);
			it--;
			printf("%d\n",(it-a.begin()+1));
		}
		else{
			vector<int>::iterator it=lower_bound(a.begin(),a.end(),x);
			printf("%d\n",(it-a.begin()+1));
		}
	}
	return 0;
}