/*#include<cstdio>
#include<algorithm>
#define NM 100001
using namespace std;
int N,M,v[NM];
int caut0(int x)
{
	int p=1,u=N,m;
	while (p!=u)
	{
		m=(p+u)>>1;
		if (v[m]>=x)
			u=m;
		else
			p=m+1;
	}
	if (v[p]==x)
		return p;
	return -1;
}
int caut1(int x)
{
	int p=1,u=N,m;
	while (p!=u)
	{
		m=(p+u)>>1;
		if (v[m]>=x)
			u=m;
		else
			p=m+1;
	}
	if (v[p]>x)
		return p-1;
	return p;
}
int caut2(int x)
{
	int p=1,u=N,m;
	while (p!=u)
	{
		m=(p+u)>>1;
		if (v[m]>=x)
			u=m;
		else
			p=m+1;
	}
	if (v[p]<x)
		return p-1;
	return p;
}
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&N);
	for (int i=1; i<=N; ++i)
		scanf("%d",&v[i]);
	//sort(v+1,v+N);
	scanf("%d",&M);
	while (M--)
	{
		int c,x;
		scanf("%d%d",&c,&x);
		if (c==0)
		{
			printf("%d\n",caut0(x));
			continue;
		}
		if (c==1)
		{
			printf("%d\n",caut1(x));
			continue;
		}
		if (c==2)
			printf("%d\n",caut2(x));
	}
	return 0;
}*/
#include<stdio.h>
#define N 100100

int v[N],n;

int caut0(int x)
{
	int p,u,m;
	p=1;
	u=n;
	while(p!=u)//cat timp intervalul in care caut are mai mult de un element
	{
		m=(p+u)/2;
		if(x<=v[m])
			u=m;
		else
			p=m+1;
	}
	if(v[p]==x)
		return p;
	return -1;
}

int caut1(int x)
{
	int p,u,m;
	p=1;
	u=n;
	while(p!=u)//cat timp intervalul in care caut are mai mult de un element
	{
		m=(p+u)/2;
		if(x<=v[m])
			u=m;
		else
			p=m+1;
	}
	if(v[p]>x)
		return p-1;
	return p;
}

int caut2(int x)
{
	int p,u,m;
	p=1;
	u=n;
	while(p!=u)//cat timp intervalul in care caut are mai mult de un element
	{
		m=(p+u)/2;
		if(x<=v[m])
			u=m;
		else
			p=m+1;
	}
	if(v[p]<x)
		return p-1;
	return p;
}

int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for (int i=1; i<=n; i++)
		scanf("%d",&v[i]);
	int m,x,i;
	scanf("%d",&m);
	while(m--){
		scanf("%d%d",&i,&x);
		if(i==0)
			printf("%d\n",caut0(x));
		if(i==1)
			printf("%d\n",caut1(x));
		if(i==2)
			printf("%d\n",caut2(x));
	}
	return 0;
}