#include <stdio.h>

int v[100001];

int bin_f(int l,int r,int val)
{
	if(l>r) return -1;
	int m=(l+r)/2;
	int b;
	if(v[m]==val)  {
		b=m;
	}
	else if(v[m]<val) {
		b=bin_f(m+1,r,val);
	}
	else {
		b=bin_f(l,m-1,val);
	}
	
	return b; 
}

int bin_search0(int l,int r,int val)
{
	int b=bin_f(l,r,val);
	while(v[b+1]==val) b++;
	return b;
}

int bin_search1(int l,int r,int val,int n)
{
	int pos_max,bs,i;
	pos_max=bin_search0(l,r,val);
	for(i=1;i<=n;i++) 
    {
	bs=bin_search0(l,r,v[i]);
	if(v[i]<val &&  bs > pos_max )  pos_max=bs;  
	} 
	while(v[pos_max+1]==val) pos_max++;
	return pos_max;
}

int bin_search2(int l,int r,int val,int n)
{
	int bs,i;
	int pos_min=100001;
	for(i=1;i<=n;i++) 
    {
	bs=bin_search0(l,r,v[i]);
	if(v[i]>=val &&  bs < pos_min ) pos_min=bs;
	}
	if(pos_min==100001) return -1; 
	while(v[pos_min-1]==val) pos_min--;
	return pos_min;
}

int main()
{
	int i,n,m,a,val;
	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++) 
    {
    scanf("%d%d",&a,&val);
    if(a==0) printf("%d\n",bin_search0(1,n,val));
    if(a==1) printf("%d\n",bin_search1(1,n,val,n));
    if(a==2) printf("%d\n",bin_search2(1,n,val,n));
    }
	
	return 0;
}