#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MaxN 100005
using namespace std;
 
FILE*IN,*OUT;

int N,Q,Type,X,v[MaxN];
int Binary_Search(int val)
{
	int lw=1,hi=N,mid,last=-1;
	while(lw<=hi)
	{
		mid=(lw+hi)>>1;
		if(v[mid]>val)
			hi=mid-1;
		else if(v[mid]<val)
			lw=mid+1;
		else lw=mid+1,last=mid;
	}
	return last;
}
int Lower_Bound(int val)
{
	int lw=1,hi=N,mid,last=0;
	while(lw<=hi)
	{
		mid=(lw+hi)>>1;
		if(v[mid]>val)
			hi=mid-1;
		else if(v[mid]<=val)
			lw=mid+1,last=mid;
	}
	return last;
}
int Upper_Bound(int val)
{
	int lw=1,hi=N,mid,last=0;
	while(lw<=hi)
	{
		mid=(lw+hi)>>1;
		if(v[mid]>=val)
			hi=mid-1,last=mid;
		else if(v[mid]<val)
			lw=mid+1,last;
	}
	return last;
}

int main()
{
    IN=fopen("cautbin.in","r");
    OUT=fopen("cautbin.out","w");

	fscanf(IN,"%d",&N);
	for(int i=1;i<=N;i++)
		fscanf(IN,"%d",&v[i]);
	fscanf(IN,"%d",&Q);
	for(int i=1;i<=Q;i++)
	{
		fscanf(IN,"%d%d",&Type,&X);
		if(Type==0)
			fprintf(OUT,"%d\n",Binary_Search(X));
		else if(Type==1)
			fprintf(OUT,"%d\n",Lower_Bound(X));
		else fprintf(OUT,"%d\n",Upper_Bound(X));
	}
    return 0;
}