#include <fstream>

using namespace std;

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

int A[100005], n, m;

int binry_search1(int st, int dr, int x)
{
	while( st < dr ){
		mid = st + ( dr - st )/2;
		if( A[mid] <= x )  st = mid + 1;
		if( A[mid] > x )   dr = mid - 1;
	}

	if( A[st] == x ) return st;
	if( A[st-1] == x ) return st-1;
	return -1;
}

int binry_search2(int st, int dr, int x)
{
	while( st < dr ){
		mid = st + ( dr - st )/2;
		if( A[mid] <= x )  st = mid + 1;
		if( A[mid] > x )   dr = mid - 1;
	}

	if( A[st] <= x ) return st;
	if( A[st-1] <= x ) return st-1;
	return -1;
}

int binry_search3(int st, int dr, int x)
{
	while( st < dr ){
		mid = st + ( dr - st )/2;
		if( A[mid] >= x )  dr = mid - 1;
		if( A[mid] < x )   st = mid + 1;
	}

	if( A[dr] == x ) return dr;
	if( A[dr+1] == x ) return dr+1;
	return -1;
}


int main()
{
	inFile >> n;

	for(int i = 1; i <= n; i++){
		inFile >> A[i];
	}

	inFile >> m;

	int op, x;
	while(m--){
		inFile >> op >> x;

		if( op == 1 ) outFile << binry_search1(1, n, x);
		if( op == 2 ) outFile << binry_search2(1, n, x);
		if( op == 3 ) outFile << binry_search3(1, n, x);
	}

	
}