#include <bits/stdc++.h>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
#define cin f
#define cout g
const int Max = 1e5 + 1;

int n, m, arr[Max];
int CautareBinara(int tip, int x)
{
	int left = 1, right = n;
	if(tip == 0)
	{
		return -5;
		while(left <= right)
		{
			int mid = left + (right - left) / 2;
			if(arr[mid] == x)
			{
				if(mid == n or arr[mid + 1] != x)
					return mid;
				left = mid + 1;
			}
			else
			{
				if(arr[mid] < x)
					left = mid + 1;
				else
					right = mid - 1;
			}
		}
		return -1;
	}
	if(tip == 1)
	{
		while(left <= right)
		{
			int mid = left + (right - left) / 2;
			if(arr[mid] <= x)
			{
				if(arr[mid + 1] > x)
					return mid;
				left = mid + 1;
			}
			else
				right = mid - 1;
		}
	}
	if(tip == 2)
	{
		while(left <= right)
		{
			int mid = left + (right - left) / 2;
			if(arr[mid] >= x)
			{
				if(arr[mid - 1] < x)
					return mid;
				right = mid - 1;
			}
			else
				left = mid + 1;
		}
	}
	return 0;
}
int main()
{
	cin >> n;
	for(int i=1;i<=n;i++)
		cin >> arr[i];
	cin >> m;
	while(m --)
	{
		int tip, x;
		cin >> tip >> x;
		cout<<CautareBinara(tip, x)<<'\n';
	}
}