#include <fstream>
#include <iostream>
using namespace std;

///// DESCRIPTION
// THIS PROGRAM FINDS ALL COMBINATIONS
// OF NUMBERS BETWEEN 1 AND n
// BY USING BACKTRACKING
/////

int binarySearch1(int, int, int, int, int[]);
int binarySearch2(int, int, int, int, int[]);
int binarySearch3(int, int, int, int, int[]);
int binarySearch(int, int, int[], int);


int main(int argc, char **argv)
{
	// INPUT
	int n, m;
	
	ifstream indata("cautbin.in");
	
	indata >> n;
	int orderedElements[n];
	for (int i = 0; i < n; i++) {
		indata >> orderedElements[i];
	}
	
	// SEARCH AND OUTPUT
	ofstream outdata("cautbin.out");
	
	indata >> m;
	int command, x;
	for (int i = 0; i < m; i++) {
		indata >> command >> x;	
		outdata << binarySearch(x, n, orderedElements, command) << "\n";
	}
	
	outdata.close();
	indata.close();
	return 0;
}

int binarySearch(int x, int n, int elements[], int command) {
	// array of function pointers pointing to the 3 different versions of binarySearch
	int (*fptr[])(int, int, int, int, int[]) = { binarySearch1, binarySearch2, binarySearch3 };
	// depending on the command value, call a different function
	return fptr[command](x, 0, n-1, n, elements);
}

int binarySearch1(int x, int ls, int ld, int n, int elements[]) {
	int middle;
	
	while (ls <= ld) {
		middle = (ls + ld) / 2;
		// if the middle element is smaller or equal,
		// increment the left limit to get the max index of x
		if(elements[middle] <= x) {
			ls = middle + 1;
		} else {
			// this will decrease either if ls = ld and el[ls] != x 
			// or if ls != ld and el[(ls + ld) / 2] > x
			ld = middle - 1;
		}
	}
	
	// at this point, ls > ld for sure by at most 1
	// --> middle = ld
	middle = (ls + ld) / 2;	
	if (elements[middle] > x) {
		// in while, ls = ld and el[middle] = x, 
		// so ls > ld by ls = middle + 1
		middle = middle - 1;
	}
	
	// middle + 1 to accommodate 
	// the fact that the array starts at 0
	return (elements[middle] == x) ? (middle + 1) : -1;
}

int binarySearch2(int x, int ls, int ld, int n, int elements[]) {
	int middle;
	
	while (ls < ld) {
		middle = (ls + ld) / 2;
		// if the middle element is smaller or equal,
		// increment the left limit to get the max index of y, y <= x
		if (elements[middle] <= x) {
			ls = middle + 1;
		} else {
			// by makind ld = middle and not middle - 1,
			// the loop will definitely stop when ls = ld
			// because at some point (ld - ls) < 2 and middle = ls
			ld = middle;
		}
	}
	
	// technically, ls = ld ALWAYS at this point
	// so middle = ls = ld
	middle = (ls + ld) / 2;
	if (elements[middle] > x) {
		// ls went one step too far in while
		// if middle was the last index of y, y <= x
		middle = middle - 1;
	}
	
	// middle + 1 to accommodate 
	// the fact that the array starts at 0
	return (middle + 1);
}

int binarySearch3(int x, int ls, int ld, int n, int elements[]) {
	int middle;
	
	while (ls < ld) {
		middle = (ls + ld) / 2;
		// if the middle element is strictly smaller
		// increment the left margin to get the min y, y >= x
		if (elements[middle] < x) {
			ls = middle + 1;
		} else {
			// this will only ever decrement if ls has reached
			// the target element
			return (ls + 1);
			ld = middle;
		}
	}
	
	// technically, ls = ld ALWAYS at this point
	// so middle = ls = ld
	middle = (ls + ld) / 2;
	
	// middle + 1 to accommodate 
	// the fact that the array starts at 0
	return (middle + 1);
}