#include <fstream>
#include <iostream>
#include <stdio.h>

using namespace std;

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

const int NMAX = 100001;

int n, queries;
int arr[NMAX];

int caut_bin0(int nr){

	int st = 0, dr = n-1;

	while(st < dr){
		int mid = st + (dr-st) / 2;
		if( arr[mid] <= nr )
			st = mid+1;
		else if( arr[mid] > nr )
			dr = mid-1;
	}
	if( arr[st] != nr)
		st--;
	if( arr[st] != nr)
		return -1;
	return st+1;
}

int caut_bin1(int nr){

	int st = 0, dr = n-1;
	while(st < dr){
		int mid = st + (dr-st) / 2;
		if( arr[mid] <= nr )
			st = mid+1;
		else if( arr[mid] > nr )
			dr = mid-1;
	}
	if( arr[st] > nr )
		st--;
	return st+1;
}

int caut_bin2(int nr){

	int st = 0, dr = n-1;
	while(st < dr){
		int mid = st + (dr-st) / 2;
		if( arr[mid] < nr )
			st = mid+1;
		else if( arr[mid] >= nr )
			dr = mid;
	}
	if(arr[st] < nr)
		st++;
	return st+1;
}

int get_result(int code, int nr){

	switch(code)
	{
		case 0: return caut_bin0(nr);
			break;
		case 1: return caut_bin1(nr);
			break;
		case 2: return caut_bin2(nr); 
			break;
	}
}



int main(){

	fin >> n;
	for(int i=0; i<n; ++i)
		fin >> arr[i];
	fin >> queries;
	int code, nr;
	for(int i=0; i<queries; ++i){
		fin >> code >> nr;
		fout << get_result(code, nr) << endl;
	}



	return 0;
}