//#include "pch.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
ifstream f("cautbin.in");
ofstream o("cautbin.out");
int n;
vector<int>v;
int binary_Search(int value)
{
	int stanga, dreapta, mijloc;
	stanga = 0;
	dreapta = n - 1;
	if (v[dreapta] == value)
	{
		return dreapta;
	}

	while (stanga <= dreapta)
	{
		mijloc = stanga + (dreapta - stanga) / 2;


		if (v[mijloc + 1] > v[mijloc])
		{
			return mijloc + 1;
		}
		if (/*v[mijloc + 1] == v[mijloc] ||*/ value >= v[mijloc])
		{
			stanga = mijloc + 1;
		}
		else
		{
			dreapta = mijloc = 1;
		}
	}

	return -1;
}

int main()
{
	f >> n;
	for (size_t i = 0; i < n; i++)
	{
		int x;
		f >> x;
		v.push_back(x);
	}
	int tests;

	f >> tests;

	while (tests--)
	{
		int type, value;
		f >> type >> value;
		switch (type)
		{
		case 0:
			o << binary_Search(value) << "\n";
			break;
		case 1:
		{
			int low = *(lower_bound(v.begin(), v.end(), value + 1));
			o << low - 1 << "\n";
		}
		break;
		case 2:
		{
			int high = *(upper_bound(v.begin(), v.end(), value - 1));
			o << high << "\n";
		}
		break;

		}
	}


}