// Cautare binara.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

int  BinSearch_0(int n, int v[], int x)
{
	int mid, st = 0, dr = n - 1, result=-1;
	while (st <= dr)
	{
		mid = (st + dr) / 2;
		if (v[mid] > x)
			dr = mid - 1;
		else 
		{
			st = mid + 1;
			if (v[mid] == x)
				result = mid;
		}
	}
	return result+1;
}

int BinSearch_1(int n, int v[], int x)
{
	int mid, st = 0, dr = n - 1, result=-2;
	while (st <= dr)
	{
		mid = (st + dr) / 2;
		if (v[mid] > x)
			dr = mid - 1;
		else 
		{
			st = mid + 1;
			if (v[mid] == x)
				result = mid;
		}
	}
	return result+1;
}

int BinSearch_2(int n, int v[], int x)
{
	int mid, st = 0, dr = n - 1, result=-2;
	while (st <= dr)
	{
		mid = (st + dr) / 2;
		if (v[mid] < x)
			st = mid + 1;
		else
		{
			dr = mid - 1;
			result=mid;
		}
	}
	return result+1;
}

int main()
{
	int N, M, v[100]; //100000
	f >> N;
	for (int i = 0; i < N; i++)
		f >> v[i];
	int ord, x;
	f >> M;
	for (int i = 0; i < M; i++)
	{
		f >> ord >> x;
		if (ord == 0)
			g << BinSearch_0(N, v, x) << "\n";
		else if (ord == 1)
			g << BinSearch_1(N, v, x) << "\n";
		else //ord==2
			g << BinSearch_2(N, v, x) << "\n";
	}
	f.close();
	g.close();
	return 0;
}