#include<stdio.h>
int v[100005], hi, lo, mid, sol, T, n;
int zero(int tar)	
{
		for(hi=n, lo=1;lo<hi;)
		{
		mid=lo+(hi-lo)/2;
		if(v[mid]<=tar)lo=mid+1;
		else hi=mid;
		}
		if(v[lo-1]!=tar)return -1;
		return lo-1;
}


int unu(int tar)
	{
		for(hi=n, lo=1;lo<=hi;)
		{
			mid=lo+(hi-lo)/2;
			if(v[mid]<=tar)sol=mid, lo=mid+1;
			else if(v[mid]>tar)hi=mid-1;
		}
		return sol;
}

int doi(int tar)
{
		for(hi=n, lo=1;lo<=hi;)
		{
			mid=lo+(hi-lo)/2;
			if(v[mid]>=tar)sol=mid, hi=mid-1;
			else if(v[mid]<tar)lo=mid+1;
		}
		return sol;
}


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]);
		for(scanf("%d", &T);T--;)
		{int x, y;
			scanf("%d %d", &y, &x);
			if(!y)printf("%d\n",zero(x));
			else if(y==1)printf("%d\n",unu(x));
			else if(y==2)printf("%d\n",doi(x));
		}
		return 0;
}