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

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

using namespace std;

vector<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);

	scanf("%lu", &n);
	v.resize(n+1);

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

	scanf("%lu", &m);
	while (m--)
	{
		scanf("%lu %lu", &i, &j);
		switch (i)
		{
		case 0:
			printf("%ld\n", BS0(n-1, j)+1);
			break;
		case 1:
			printf("%lu\n", BS1(n-1, j)+1);
			break;
		case 2:
			printf("%lu\n", BS2(n-1, j)+1);
			break;
		}
	}

	return 0;
}