#include<cstdio>
using namespace std;
int n,m,x,y,a[100001];
int bin0(int s, int d, int k)
{
	int j;
	while(s<=d)
	{
		j=(s+d)/2;
		if(a[j]<=k) s=j+1;
		else d=j-1;
	}
	j=(s+d)/2;
	if(a[j]>k) j--;
	if(a[j]==k) return j;
	else return -1;
}
int bin1(int s, int d, int k)
{
	int j;
	while(s<d)
	{
		j=(s+d)/2;
		if(a[j]<=k) s=j+1;
		else d=j;
	}
	j=(d+s)/2;
	if(a[j]>k) j--;
	return j;	
}
int bin2(int s, int d, int k)
{
	int j;
	while(s<d)
	{
		j=(s+d)/2;
		if(a[j]<k) s=j+1;
		else d=j;
	}
	j=(d+s)/2;
	if(a[j]<k) j++;	
	return j;
}
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d\n",&n);
	for(int i=1;i<n;i++) scanf("%d ",&a[i]);
	scanf("%d\n",&a[n]);
	scanf("%d\n",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d\n",&x,&y);
		if(x==0) printf("%d\n",bin0(1,n,y));
		else if(x==1)printf("%d\n",bin1(1,n,y));
		else if(x==2) printf("%d\n",bin2(1,n,y));
	}
	fclose(stdin);fclose(stdout);
	return 0;
}