#include <fstream>
#include <iostream>
#include <iterator>
using namespace std;

const int SIZE=100000;
int n,m;
int v[SIZE];

int bin1(int x)
{
	bool gasit=false;
	int start,
			end;

	start=0;
	end=n;
	int mid;

	int pozitie=-1;
	while(start<=end)
	{
		mid=start+(end-start)/2;

		if(v[mid]==x)
		{
			pozitie=mid;
			gasit=true;
			if(v[mid+1]==x)
				start=mid+1;
			else
				break;
		}
		else if(v[mid]<x)
			start=mid+1;
		else if(v[mid]>x)
			end=mid-1;
	}

	return pozitie;
}

int bin2(int x)
{
	bool gasit=false;
	int start,
			end;

	start=0;
	end=n;
	int mid;

	int pozitie=-1;
	while(start<=end)
	{
		mid=start+(end-start)/2;

		if(v[mid]<=x)
		{
			pozitie=mid;
			if(v[mid+1]<=x)
				start=mid+1;
			else
				break;
		}
		else if(v[mid]>x)
			end=mid-1;
	}

	return pozitie;
}

int bin3(int x)
{
	bool gasit=false;
	int start,
			end;

	start=0;
	end=n;
	int mid;

	int pozitie=-1;
	while(start<=end)
	{
		mid=start+(end-start)/2;
		if(v[mid]>=x)
		{
			pozitie=mid;
			if(v[mid-1]>=x)
				end=mid-1;
			else
				break;
		}
		else if(v[mid]<x)
			start=mid+1;
	}

	return pozitie;
}
int main()
{
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");

	f>>n;
	for(int i=1; i<=n; i++)
		f>>v[i];
	f>>m;
	int op,nr;

	for(int i=1; i<=m; i++)
	{
		f>>op>>nr;
		if(op==0)
			g<<bin1(nr)<<endl;
		else if(op==1)
			g<<bin2(nr)<<endl;
		else
			g<<bin3(nr)<<endl;
	}
	return 0;
}