/*
 * Autor: Paul Herman
 * Problema: cautare binara
 * Data: 17.01.2012
 * Punctaj: -
 * Link: http://www.infoarena.ro/problema/cautbin
 */
#include <fstream>
#include <iostream>
using namespace std;

int v[100000]; //Vectorul de numere
int n; //Nr de elemente
int m; //Nr de queryuri
int operatie; //Tipul operatiei
int x; //Valoarea cautata
int rezultat; //Rezultatul operatiei

int cautare()
{
	int pas = n >> 2;
	int i = 0;
	for (i = 0; pas > 0; pas >>= 1)
		if (((i + pas) < n) && (v[i + pas] <= x))
			i += pas;
	return i;
}
int main()
{
	ifstream fin("cautbin.in");
	ofstream fout("cautbin.out");
	fin >> n;
	for (int i = 0; i < n; i++)
		fin >> v[i];
	fin >> m;
	for (int i = 0; i < m; i++)
	{
		fin >> operatie >> x;
		rezultat = cautare();
		cout << rezultat << ' ';
		if (operatie == 0)
		{
			if (v[rezultat] != x)
				fout << "-1\n";
			else
				while (v[rezultat] == x)
					rezultat++;
				fout << (rezultat) << '\n';
		}
		else if (operatie == 1)
		{
			while (v[rezultat] <= x)
				rezultat++;
			fout << rezultat << '\n';			
		}
		else
		{
			while (v[rezultat] >= x)
				rezultat--;
			rezultat++;
			fout << rezultat + 1 << '\n';
		}
	}
	fin.close();
	fout.close();
	return 0;
}