#include<iostream>
#include<stdio.h>
using namespace std;
int mid, N;
inline int bs0(unsigned int *v, int key){
	int min = 0, max = N-1;
	while(min <= max){
		mid = (min+max)/2;
		if(v[mid] == key){
			while((mid+1 < max) && (v[mid + 1] == key))
				min = mid + 1;
			return mid;
		}
		if(v[mid] <  key){
			min = mid + 1;
			continue;
		}
		if(v[mid] > key){
			max = mid - 1;
			continue;
		}
	}
	return -1;
}
int bs1(unsigned int *v, int key){
	int min = 0, max = N-1;
	while(min <= max){
		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;
			continue;
		}
		if(v[mid] > key){
			max = mid - 1;
			continue;
		}
	}
	return mid;
}
int bs2(unsigned int *v, int key){
	int min = 0, max = N-1;
	while(min <= max){
		mid = (min+max)/2;
		if((v[mid] >= key) && (v[mid-1] < key))
			return mid;
		if((v[mid] >= key) && (v[mid-1] >= key)){
			max = mid - 1;
			continue;
		}
		if(v[mid] < key){
			min = mid + 1;
			continue;
		}
	}
	return mid;
}
int main(){
	clock_t t;
	t = clock();
	int M, i, select, poz;
	unsigned int *v, x;
	freopen("problema_cautbin/grader_test10.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);
			if(poz != -1)
				cout << poz + 1 << endl;
			else
				cout << poz << endl;
			continue;
		}
		if(select == 1){
//			cout << "select 1" << endl;
			cout << bs1(v, x) + 1 << endl;
			continue;
		}
		if(select == 2){
//			cout << "select 2" << endl;
			cout << bs2(v, x) + 1 << endl;
			continue;
		}
	}
//	cout << ((float)(clock()-t)) / CLOCKS_PER_SEC << endl;
	return 0;
}