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

int bs0(unsigned int *v, int key, int min, int max){
	int mid;
	while(min <= max){
		mid = (min+max)/2;
		if(v[mid] == key){
			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, int max){
	int mid;
	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, int max){
	int mid;
	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(){
	int N, M, i, select, poz;
	unsigned int *v, x;
	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){
//				cout << "select 0" << endl;
				poz = bs0(v, x, poz+1, N-1);
			}
			if(poz != -1)
				cout << poz + 1 << endl;
			else
				cout << poz << endl;
		}
		if(select == 1){
//			cout << "select 1" << endl;
			cout << bs1(v, x, 0, N-1) + 1 << endl;
		}
		if(select == 2){
//			cout << "select 2" << endl;
			cout << bs2(v, x, 0, N-1) + 1 << endl;
		}
	}
	return 0;
}