#include<iostream>
#include<stdio.h>
using namespace std;

int bs0(unsigned int *v, int key, int min, int max){
	int mid;
	while(min <= max){
//		cout << "bs0";
		mid = (min+max)/2;
		if(v[mid] == key)
			return mid;
		if(v[mid] <  key)
			min = mid + 1;
		if(v[mid] > key)
			max = mid;
		if((min == max) && (v[min] != key))
			return -1;
//		cout << " max= " << max << " min= " << min << " x= " << key << " v[mid]= " << v[mid] << endl;
	}
	return -1;
}
int bs1(unsigned int *v, int key, int min, int max){
	int mid;
	while(min <= max){
//		cout << "bs1";
		mid = (min+max)/2;
		if((v[mid] <= key) && (v[mid+1] > key))
			return mid;
		if((v[mid] <= key) && (v[mid+1] <= key))
			min = mid + 1;
		if(v[mid] > key)
			max = mid;
		if(min == max)
			return min;
	}
	return mid;
}
int bs2(unsigned int *v, int key, int min, int max){
	int mid;
	while(min <= max){
//		cout << "bs2 ";
		mid = (min+max)/2;
		if((v[mid] >= key) && (v[mid-1] < key))
			return mid;
		if((v[mid] >= key) && (v[mid-1] >= key))
			max = mid;
		if(v[mid] < key)
			min = mid + 1;
		if(min == max)
			return min;
//		cout << "max= " << max << " min= " << min << " x= " << key << " v[mid]= " << v[mid] << endl;
	}
	return mid;
}
int main(){
	int N, M, i, select, poz;
	unsigned int *v, x;
	freopen("problema_cautbin/grader_test2.in", "r", stdin);
//	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	
	cin >> N;
	v = new unsigned int[N];
	for(i = 0; i < N; i++)
		cin >> v[i];
	cin >> M;
	
	for(i = 0; i < M; i++){
		cin >> select;
		cin >> x;
		if(select == 0){
			poz =  bs0(v, x, 0, N-1);
			while(v[poz+1] == x)
				poz = bs0(v, x, 0, N-1);
			if(poz != -1)
				cout << poz + 1 << endl;
			else
				cout << poz << endl;
		}
		if(select == 1)
			cout << bs1(v, x, 0, N-1) + 1 << endl;
		if(select == 2)
			cout << bs2(v, x, 0, N-1) + 1 << endl;
	}
	return 0;
}