#include <iostream>
#include <vector>
#include <bits/stdc++.h>
#include <algorithm>
// #include <chrono>

using	namespace std;
using namespace std::chrono; 

long long int	v[100002];
ifstream	f("cautbin.in");
ofstream	g("cautbin.out");
int			op;
long long int	n, m;
long long int nr, x;

/*
0 x - cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir
1 x - cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x
2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x
*/

long long int	cautbin()
{
	long long int dr = n - 1, st = 0;
	long long int mij;
	
	if (op == 0)
	{
		while (st <= dr)
		{
			mij = st + (dr - st) / 2;

			if (v[mij] == x && mij == (n - 1) || v[mij] == x && v[mij + 1] != x)
				return mij + 1;
			
			if (v[mij] <= x)
				st = mij + 1;
			else
				dr = mij - 1;
			
			mij = st / 2 + dr / 2;
		}
		
		return -1;
	}
	else if (op == 1)
	{
		while (st <= dr)
		{
			mij = st + (dr - st) / 2;
			
			if (v[mij] <= x && mij == (n - 1) || v[mij] <= x && v[mij + 1] > x)
				return mij + 1;
			
			if (v[mij] <= x)
				st = mij + 1;
			else
				dr = mij - 1;
			
			mij = st / 2 + dr / 2;
		}
		
		return -1;
	}
	else if (op == 2)
	{
		while (st <= dr)
		{
			mij = st + (dr - st) / 2;
			
			if (v[mij] >= x && mij == 0 || v[mij] >= x && v[mij - 1] < x)
				return mij + 1;
			
			if (v[mij] >= x)
				dr = mij - 1;
			else
				st = mij + 1;
			
			mij = st / 2 + dr / 2;
		}
		
		return -1;
	}
}

int	main()
{
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
	f >> n;
	//auto start = high_resolution_clock::now(); 

	
	for (register long long int index = 0; index < n; index++)
	{
		f >> v[index];
	}
	
	f >> m;
	for (register long long int index = 0; index < m; index++)
	{
		f >> op >> x;
		g << cautbin() << '\n';
	}

	/*
	auto stop = high_resolution_clock::now(); 
	auto duration = duration_cast<microseconds>(stop - start); 
	cout << '\n' << "Time taken by function: " << duration.count() << " microseconds" << '\n'; 
	*/
	return	0;
}