#include<iostream>
#include<fstream>
using namespace std;
int v[100001],n;
int cautbin0(int x)
{
	int sol = -1, poz;
	int min=1, max=n;
	while(min!=max)
	{
		poz=(min+max)/2;
		if(v[poz]>x)
			max=poz;
		else if(v[poz]<=x)
			min=poz+1;
		if(v[poz] == x)
			sol = poz;
	}
	if(v[min] == x)
		sol = min;
	return sol;
}
int cautbin1(int x)
{
	int min=1, max=n, sol;
	while(min!=max)
	{
		int poz=(min+max)/2;
		if(v[poz]>x)
			max=poz;
		else if(v[poz]<=x)
		{
			min=poz+1;
			sol=poz;
		}
	}
	if(v[min] <= x)
		sol = min;
	return sol;
}
int cautbin2(int x)
{
	int min=1, max=n, sol;
	while(min!=max)
	{
		int poz=(min+max)/2;
		if(v[poz]>=x) {
			max=poz;
			sol = poz;
		}
		else 
			min=poz+1;
			
	}
	if(v[min] <= x)
		sol = min;
	return sol+1;
}
int main()
{
	ifstream g("cautbin.in");
	ofstream h("cautbin.out");
	int m,tip,x;
	g>>n;
	for(int i=1;i<=n;i++)
	{
		g>>v[i];
	}
	g>>m;
	for(int k=1;k<=m;k++)
	{
		g>>tip>>x;
		if( tip == 0)
			h<<cautbin0(x)<<"\n";
		else if(tip ==1 )
			h<<cautbin1(x)<<"\n";
		else h<<cautbin2(x)<<"\n";
	}
}