#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

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

int a[100001];
int n;
int m;

int main()
{
	fin >> n;
	for(int i = 1; i <= n; ++i)
		fin >> a[i];
	
	fin >> m;
	int x, y;
	for(int i = 1; i <= m; ++i)
	{
		fin >> x >> y;
		if( x == 0)
			if( binary_search(a+1, a+n+1, y) == false)
				fout << -1 << '\n';
			else
				fout << *upper_bound(a+1, a+n+1, y) - 1 << '\n';;
			
		if( x == 1)
		    fout << *lower_bound(a+1, a+n+1, y+1) - 1 << '\n';;
		
		if(x == 2)
			fout << *upper_bound(a+1, a+n+1, y-1) -1 << '\n';;
	}

return 0;
}