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

using	namespace std;
using namespace std::chrono; 

/*
https://www.infoarena.ro/problema/cautbin

Se da un sir de numere ordonat crescator cu N elemente, si se cere sa se raspunda la M intrebari de tipul:
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

*/

vector<long long int>	v;
ifstream	f("cautbin.in");
ofstream	g("cautbin.out");
int			op;
long int	n, m;
long long int nr, x;

long int	cautbin()
{
	long int dr = v.size() - 1, st = 0;
	long int mij = st / 2 + dr / 2;
	
	while (st <= dr)
	{
		if (v[mij] == x)
		{
			if (op == 0)
			{
				while (v[mij] == x)
					mij++;
				return mij;
			}
			else if (op == 1)
			{
				while (v[mij] == x)
					mij++;
				return (mij);
			}
			else if (op == 2)
			{
				while (v[mij] == x)
					mij--;
				return (mij + 2);
			}
		}
		else if (v[mij] < x)
			st = mij + 1;
		else
			dr = mij - 1;

		mij = st / 2 + dr / 2;
	}
	
	if (op == 0)
		return -1;
	else if (op == 1)
	{
		if (v[mij] > x)
		{
			while (v[mij] > x)
				mij--;
			return (mij + 1);
		}
		else if (v[mij] < x)
		{
			while (v[mij] < x)
				mij++;
			return (mij);
		}
	}
	else if (op == 2)
	{
		if (v[mij] > x)
		{
			while (v[mij] > x)
				mij--;
			return (mij + 1);
		}
		else if (v[mij] < x)
		{
			while (v[mij] < x)
				mij++;
			return (mij + 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 >> nr;
		v.push_back(nr);
	}
	
	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;
}