/*
 * cautbin.cpp
 *
 *  Created on: Nov 6, 2008
 *      Author: stefan
 */

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

unsigned long int* v;

long int BS0(unsigned long int hi, unsigned long int search)
{
	unsigned long int lo = 0, mid;
	while (lo <= hi)
	{
		mid = lo + (hi - lo) / 2;
		if (v[mid] < search)
			lo = mid + 1;
		else
			hi = mid - 1;
	}

	if (v[mid] != search)
		return -2;

	while(v[++mid] == search);

	return mid-1;
}

unsigned long int BS1(unsigned long int hi, unsigned long int search)
{
	unsigned long int lo = 0, mid;
	while(lo<=hi)
	{
		mid = lo + (hi - lo) / 2;
		if(v[mid] < search)
			lo = mid + 1;
		else
			hi = mid - 1;
	}
	if (v[mid] != search)
		return mid-1;
	return mid;
}

unsigned long int BS2(unsigned long int hi, unsigned long int search)
{
	unsigned long int lo = 0, mid;
	while(lo<=hi)
	{
		mid = lo + (hi - lo) / 2;
		if(v[mid] < search)
			lo = mid + 1;
		else
			hi = mid - 1;
	}

	return mid;
}

int main()
{
	unsigned long int m, n, i, j;

	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);

	cin >> n;
	v = new unsigned long int [n];

	for (i = 0; i < n; ++i)
		cin >> v[i];

	cin >> m;
	while (m--)
	{
		cin >> i >> j;
		switch (i)
		{
		case 0:
			cout << BS0(n-1, j)+1 << endl;
			break;
		case 1:
			cout << BS1(n-1, j)+1 << endl;
			break;
		case 2:
			cout << BS2(n-1, j)+1 << endl;
			break;
		}
	}

	return 0;
}