#include <stdio.h>
#include <stdlib.h>
#define SIZE 100000
int n,m;
int v[SIZE];


typedef char bool;

const int false=0;
const int true=1;
int bin1(int x)
{
	bool gasit=false;
	int mid;
	int start,
			end;
	int pozitie=-1;

	start=0;
	end=n;



	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;
	int mid;
	int pozitie=-1;
	start=0;
	end=n;


	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;

	int mid;
	int pozitie=-1;
	start=0;
	end=n;
	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()
{
	int i;
	int m;
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for(i=1; i<=n; i++)
		scanf("%d",&v[i]);
	scanf("%d",&m);


	for(i=1; i<=m; i++)
	{
		int op;
		int nr;
		scanf("%d %d",&op,&nr);
		if(op==0)
			printf("%d\n",bin1(nr));
		else if(op==1)
			printf("%d\n",bin2(nr));
		else
			printf("%d\n",bin3(nr));

	}
	return 0;
}