#include<stdio.h>
int n, m, x[100000];

int cauta0(int b,int st, int sf) //p start, p sfarsit
{	
	int mij;
	while(st<=sf)
	{
		mij=(st+sf)/2;
		if(b>=x[mij])
			st=mij+1;
		else
			sf=mij-1;
	}
	mij=(st+sf)/2;
	if(x[mij]>b) mij--;
	if(x[mij]==b) 
		return mij;
	return -1;
}

int cauta1(int b,int st, int sf)
{
	int mij;
	while(st<sf)
	{
		mij=(st+sf)/2;
		if(b>=x[mij])
			st=mij+1;
		else
			sf=mij;
	}
	mij=(st+sf)/2;
	if(x[mij]>b)
		mij--;
	return mij;
}

int cauta2(int b,int st, int sf)
{
	int mij;
	while(st<sf)
	{
		mij=(st+sf)/2;
		if(b<=x[mij])
			sf=mij-1;
		else
			st=mij+1;
	}
	mij=(st+sf)/2;
	if(x[mij]<b)
		mij++;
	return mij;
}
	
int main()
{
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	scanf("%d", &n);
	int i, a, b;
	
	for(i=1;i<=n;i++)
		scanf("%d", &x[i]);
	scanf("%d", &m);
	
	for(i=1;i<=m;i++)
	{
		scanf("%d %d", &a, &b);
		if(a==0)
			printf("%d\n", cauta0(b,1,n));
		if(a==1)
			printf("%d\n", cauta1(b,1,n));
		if(a==2)
			printf("%d\n", cauta2(b,1,n));
	}
	return 0;
}