#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define ll long long 
#define ull unsigned long long 
#define nmax 100006
#define MOD 9901 
#define INF 2123456789
//#define fin cin 
//#define fout cout 

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, m;
int a[nmax];

int CB0(int x)
{
	int st, dr, m, p;
	st = 1; dr = n; p = n + 1;
	while (st <= dr)
	{
		m = (st + dr) / 2;
		if (a[m] == x)
		{
			p = m;
			st = m + 1;
		}
		else if (a[m] < x)
			st = m + 1;
		else
			dr = m - 1;
	}
	return p;
}

int CB1(int x)
{
	int st, dr, m, p;
	st = 1; dr = n; p = n + 1;
	while (st <= dr)
	{
		m = (st + dr) / 2;
		if (a[m] <= x)
		{
			p = m;
			st = m + 1;
		}
		else
			dr = m - 1;
	}
	return p;
}

int CB2(int x)
{
	int st, dr, m, p;
	st = 1; dr = n; p = n + 1;
	while (st <= dr)
	{
		m = (st + dr) / 2;
		if (a[m] >= x)
		{
			p = m;
			dr = m - 1;
		}
		else
			st = m + 1;
	}
	return p;
}

int main()
{
	int i, x, t, p;
	fin >> n;
	for (i = 1; i <= n; i++)
		fin >> a[i];
	fin >> m;
	// t = 0 => cea mai din drp poz unde a[i] = x
	// t = 1 => cea mai din drp poz unde a[i] <= x
	// t = 2 => cea mai din stg poz unde a[i] >= x
	for (i = 1; i <= m; i++)
	{
		fin >> t >> x;
		if (t == 0)
		{
			p = CB0(x);
			if (p == n + 1)
				fout << "-1\n";
			else
				fout << p << "\n";
		}
		else if (t == 1)
			fout << CB1(x) << "\n";
		else
			fout << CB2(x) << "\n";
	}
	fin.close();
	fout.close();
	return 0;
}