#include <cstdio>
#include <iostream>

using namespace std;

#define maxN 100005

int N , M , A[maxN];


int search0 (int x)
{
	int lo = -1 , hi = N + 1 , mid;
	
	while (hi - lo > 1)
	{
		mid = (hi + lo) / 2;
		
		if (A[mid] <= x)
			lo = mid;
		
		else hi = mid;
	}
	
	if (lo == -1 || A[lo] != x)
		return -1;
	
	return lo;
}


int search1 (int x)
{
	int lo = -1 , hi = N + 1 , mid;
	
	while (hi - lo > 1)
	{
		mid = (hi + lo) / 2;
		
		if (A[mid] <= x)
			lo = mid;
		
		else hi = mid;
	}
	
	
	return lo;
}


int search2 (int x)
{
	int lo = -1 , hi = N + 1 , mid;
	
	while (hi - lo > 1)
	{
		mid = (hi + lo) / 2;
		
		if (A[mid] < x)
			lo = mid;
		
		else hi = mid;
	}
	
	
	return hi;
}


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);
	
	
	int cod , x;
	
	while (M --)
	{
		scanf ("%d %d" , &cod , &x);
		
		if (cod == 0)
			printf ("%d\n" , search0 (x) );
		
		else if (cod == 1)
			printf ("%d\n" , search1 (x) );
		
		else
			printf ("%d\n" , search2 (x) );
	}
	
	return 0;
}