#include <iostream>
#include <string>

using namespace std;

#define NM 100005

int N, M, A[NM];

int cauta0(int x)
{
	int st = 1, dr = N;
	
	while (st < dr - 1)
	{
		int mij = (st + dr)/2;
		
		if (A[mij] == x) st = mij;
		else if (A[mij] < x) st = mij + 1;
		else dr = mij - 1;
	}	
	
	if (A[dr] == x) return dr;
	else if (A[st] == x) return st;
	else return -1;
}

int cauta1(int x)
{
	int st = 1, dr = N;
	
	while (st < dr - 1)
	{
		int mij = (st + dr)/2;
		
		if (A[mij] <= x) st = mij;
		else dr = mij - 1;
	}	
	
	if (A[dr] <= x) return dr;
	else return st;
}

int cauta2(int x)
{
	int st = 1, dr = N;
	
	while (st < dr)
	{
		int mij = (st + dr)/2;
		
		if (A[mij] >= x) dr = mij;
		else st = mij + 1;
	}	
	
	return st;
}

int main()
{
	freopen ("cautbin.in", "r", stdin);
	freopen ("cautbin.out", "w", stdout);
	
	scanf ("%d", &N);
	
	for (int i = 1; i <= N; ++i) scanf ("%d", &A[i]);
	
	scanf ("%d", &M);
	
	for (int i = 1; i <= M; ++i)
	{
		int op, x;
		scanf ("%d %d", &op, &x);
		
		if (op == 0) printf ("%d\n", cauta0(x));
		else if (op == 1) printf ("%d\n", cauta1(x));
		else printf ("%d\n", cauta2(x));
	}	
	
	return 0;
}