/*
 * cautare.cpp
 *
 *  Created on: Mar 12, 2013
 *      Author: Sorin
 */
#include<iostream>
#include<fstream>
using namespace std;

int n, m, tab[100002], i, caz, val;

int f0(int tab[], int n, int val)
{
	int ls = 0, ld = n-1, mij, poz = -1;
	while(ls <= ld)
	{
		mij = ls + (ld - ls) / 2;
		if(val == tab[mij])
		{
			poz = mij;
			break;
		}
		else
		{
			if(val < tab[mij])
				ld = mij - 1;
			else
				ls = mij + 1;
		}
	}
	if(ls > ld)
		return -1;
	else
	{
		while(tab[poz] == val)
			poz++;
		return poz;
	}
}
//cea mai mare pozitie pe care se afla un element
//cu valoarea mai mica sau egala cu x in sir.
int f1(int tab[], int n, int x)
{
	int ls = 0, ld = n-1, mij, poz = -1;
	while(ls <= ld)
	{
		mij = ls + (ld - ls) / 2;
		if(tab[mij] <= x)
		{
			poz = mij;
			ls = mij + 1;
		}
		else
		{
			ld = mij - 1;
		}
	}

	return poz + 1;
}

//cea mai mica pozitie pe care se afla
//un element cu valoarea mai mare sau egala cu x in sir.
int f2(int tab[], int n, int x)
{
	int ls = 0, ld = n-1, mij, poz;
	while(ls <= ld)
	{
		mij = ls + (ld - ls) / 2;
		if(tab[mij] >= x)
		{
			poz = mij;
			ld = mij - 1;
		}
		else
		{
			ls = mij + 1;
		}
	}
	return poz + 1;
}

int main()
{
	
	ifstream fin("cautbin.in");
	ofstream fout("cautbin.out");
	fin>>n;
	for(i = 0; i < n; i++)
		fin>>tab[i];
	fin>>m;
	for(i = 0; i < m; i++)
	{
		fin>>caz>>val;
		switch(caz)
		{
		case 0:
			fout<<f0(tab, n, val)<<endl;
			break;
		case 1:
			fout<<f1(tab, n, val)<<endl;
			break;
		case 2:
			fout<<f2(tab, n, val)<<endl;
		}
	}
	fin.close();
	fout.close();
	return 0;
}