#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>

using namespace std;

#define maxN 100005
#define inf (1 << 30)

int A[maxN], N;


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


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


int bin_Search2 (int x)
{
	int st = 1, dr = N;
	int sol = inf;
	
	while (st <= dr)
	{
		int mid = (st + dr) / 2;
		
		if (A[mid] >= x)
		{
			sol = min (sol, mid);
			dr = mid - 1;
		}
		else st = mid + 1;
	}
	
	return sol;
}


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]);
	
	int M;
	
	scanf ("%d", &M);
	
	while (M --)
	{
		int type, x;
		
		scanf ("%d %d", &type, &x);
		
		if (! type)	printf ("%d\n", bin_Search0 (x));
		if (type == 1) printf ("%d\n", bin_Search1 (x));
		if (type == 2) printf ("%d\n", bin_Search2 (x));
	}
	
	return 0;
}