#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <vector>

#define MAX 1000003

using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");

int N, M;
int arr[MAX];


int Search0(int x){

	int left = 0, right = N+1;
	while(right - left > 1){
		int mid = (right + left)/2;
		if(x >= arr[mid])
			left = mid;
		else right = mid;
	}

	if(left == 0 || x != arr[left])
		return -1;


	return left;
}

int Search1(int x){

	int left = 0, right = N+1;
	while(right - left > 1){
		int mid = (right + left)/2;
		if(x >= arr[mid])
			left = mid;
		else right = mid;
	}

	return left;
}


int Search2(int x){

	int left = 0, right = N+1;
	while(right - left > 1){
		int mid = (right + left)/2;
		if(x <= arr[mid])
			right = mid;
		else left = mid;
	}

	return right;
}


void binarySearch(){

	in >> N;

	int op, x, r;

	for(int i = 1; i <= N; ++i){
		in >> arr[i];
	}

	in >> M;

	for(int i = 0; i < M; ++i){

		in >> op >> x;
		switch(op){
			
			case(0):
				r = Search0(x);
				out << r << "\n";
				break;

			case(1):
				r = Search1(x);
				out << r << "\n";
				break;

			case(2):
				r = Search2(x);
				out << r << "\n";
				break;

			default:
				out << "Incorrect operation!\n";
		}
	}
}

int main(){

	binarySearch();

	return 0;
}