#include <cstdio>
#include <iostream>

using namespace std;


#define maxN 100005

int N , A[maxN] , M;


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


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


int caut2 (int x)
{
	int lo = 0 , hi = N , mid;
	
	while (hi - lo > 1)
	{
		mid = (lo + hi) / 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" , caut0 (x));
		
		else if (cod == 1)
			printf ("%d\n" , caut1 (x));
		
		else printf ("%d\n" , caut2 (x));
	}
	
	
	return 0;
}