#include<iostream>
#include<fstream>
using namespace std;
int v[100001],n;
int cautbin0(int x)
{
	int sol = -1;
	int min=1, max=n;
	if(v[1]==x) sol=1;
	if(v[n]==x) sol=n;
	else
		while(min!=max)
		{
			int poz=(min+max)/2;
			if(v[poz]>x)
				max=poz;
			else if(v[poz]<=x)
				min=poz+1;
			if(v[poz] == x)
				sol = poz;
		}
	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;
		}
		else
		{
			min=poz+1;
			sol=poz;
		}
	}
	if(v[sol+1]<=x)sol++;
	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;
		else if(v[poz]<x)
		{
			min=poz+1;
			sol=poz;
		}
		else
		{
			max=poz;
			sol=poz;
		}
	}
	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";
	}
}