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

ifstream f("cautbin.in");
ofstream g("cautbin.out");
const unsigned int SIZE=100000;


#define INF 0x7fffffff;

int v[SIZE];
struct
{
  int op;
  int  numar;
}op;

int n;
int m;

int bs1(int x)
{
	int start,
			end;

	start=1;
	end=n;
	bool gasit=false;
	int mid;
	while(start<=end)
	{
		mid=start+(end-start)/2;
		if(v[mid]==x)
		{
			gasit=true;
			break;
		}
		else if(v[mid]<x)
			start=mid+1;

		else if(v[mid]>x)
			end=mid;
	}
	if(gasit==false)
		return -1;

	while(v[mid]==x)
		mid++;
	return mid-1;

}

int bs2(int x)
{
	int start=1,
			end=n;

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

	while(v[mid]==x)
		mid++;
	return mid-1;
}

int bs3(int x)
{
	int start=1,
			end=n;

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

	while(v[mid]==x)
		mid--;
	return mid+1;
}

int main()
{
  f>>n;
  for(int i=1; i<=n; i++)
    f>>v[i];
  f>>m;

	for(int i=1; i<=m; i++)
	{
		f>>op.op>>op.numar;
		if(op.op==0)
			g<<bs1(op.numar)<<endl;
		else if(op.op==1)
			g<<bs2(op.numar)<<endl;
		else
			g<<bs3(op.numar)<<endl;
	}

  return 0;
}