#include <fstream>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <stack>
#include <cstring>
#include <queue>
#define MAX 100000
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
//int32_t myVector[MAX + 27],n, m;
int n, a[100003];
int cautbin0(int x)
{
	int st, dr, mij, poz = -1;
	st = 1;
	dr = n;
	while (st <= dr)
	{
		mij = (st + dr) / 2;
		if (x == a[mij])
		{
			poz = mij;
			st = mij + 1;
		}
		if (x<a[mij])
			dr = mij - 1;
		if (x>a[mij])
			st = mij + 1;
	}
	return poz;
}
int cautbin1(int x)
{
	int st, dr, mij, poz = -1;
	st = 1;
	dr = n;
	while (st <= dr)
	{
		mij = (st + dr) / 2;
		if (a[mij] <= x)
		{
			poz = mij;
			st = mij + 1;
		}
		if (a[mij]>x)
			dr = mij - 1;
	}
	return poz;
}

int cautbin2(int x)
{
	int st, dr, mij, poz = -1;
	st = 1;
	dr = n;
	while (st <= dr)
	{
		mij = (st + dr) / 2;
		if (a[mij] >= x)
		{
			poz = mij;
			dr = mij - 1;
		}
		if (a[mij]<x)
			st = mij + 1;
	}
	return poz;
}

int main()
{
	int i, m, tip, x;
	fin >> n;
	for (i = 1; i <= n; i++)
		fin >> a[i];
	fin >> m;
	for (i = 1; i <= m; i++)
	{
		fin >> tip >> x;
		if (tip == 0)
			fout << cautbin0(x) << "\n";
		if (tip == 1)
			fout << cautbin1(x) << "\n";
		if (tip == 2)
			fout << cautbin2(x) << "\n";
	}

	return 0;
}