#include <iostream>
#include <fstream>

using namespace std;

#define NMAX 100005

int A[NMAX], N, M;

int search1(int x)
{
	int l = 1, r = N, m;
	while(l <= r)
	{
		m = l + (r-l)/2;
		if(A[m] == x)
		{
			while(m <= N && A[m] == x)
				++m;
			return m-1;
		}
		else if(A[m] < x)
		{
			l = m + 1;
		}
		else
		{
			r = m - 1;
		}
	}
	return -1;
}

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

int search3(int x)
{
	int l = 1, r = N, m;
	while(l <= r)
	{
		m = l + (r-l)/2;
		if(A[m] >= x)
		{
			if(m == 0)
				return m;
			if(A[m-1] < x)
				return m;
			else 
				r = m - 1;
		}
		else
		{
			l = m + 1;
		}
	}
	return -1;
}

int search(int code, int el)
{
	switch(code + 1)
	{
		case 1:
			return search1(el);
			break;
		case 2:
			return search2(el);
			break;
		case 3:
			return search3(el);
			break;
	}
	return -1;
}

int main()
{
	freopen("cautbin.in", "rt", stdin);
	freopen("cautbin.out", "wt", stdout);
	
	scanf("%d", &N);
	
	for(int i = 1; i <= N; ++i)
	{
		scanf("%d", &A[i]);
	}
	
	scanf("%d", &M);
	
	for(int i = 0; i < M; ++i)
	{
		int code, el;
		scanf("%d %d", &code, &el);
		printf("%d\n", search(code, el));
	}
	
	return 0;
}