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

int main (int argc, char const *argv[])
{
	ifstream in ("cautbin.in");
	int n; in >> n;
	vector<int> v(n + 1);
	for (int i = 1; i <= n; i++)
		in >> v[i];
	
	int k; in >> k;
	vector<int> type(k), target(k);
	for (int i = 0; i < k; i++)
	{
		in >> type[i] >> target[i];
	}
	in.close();
	
	/*
	for (int i = 0; i < k; i++)
	{
	 	cout << type[i] << ' ' << target[i] << '\n';
	}
	cout << '\n';
	*/
	
	ofstream out ("cautbin.out");
	for (int i = 0; i < k; i++)
	{
		int tip = type[i];
		int tar = target[i];
		
		if (tip == 0)
		{
			int x = *upper_bound(v.begin() + 1, v.end(), tar) - 1;
			if (x <= n && x >= 1 && v[x] == tar)
				out << x << '\n';
			else
				out << -1 << '\n';
		}
		else if (tip == 1)
			out << *lower_bound(v.begin() + 1, v.end(), tar + 1) - 1 << '\n';
		else
			out << *upper_bound(v.begin() + 1, v.end(), tar - 1) - 1 << '\n';
	}
	out.close();
	
	return 0;
}