//cautare binara bc

#include <stdio.h>
#define nmax 100001

int a[nmax],n,m;

int main()
{
	int i,x,val,step,j;
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	scanf("%d",&m);
	for(step=1;step<=n;step*=2);
	for(int k=1;k<=m;k++)
	{
		scanf("%d%d",&x,&val);
		if(x==0 || x==1)
		{
			for(j=step,i=0;j;j/=2)
				if(i+j<=n && a[i+j]<=val)
					i+=j;
			if(x==0 && a[i]!=val)
				printf("-1\n");
			else
				printf("%d\n",i);
		}
		else
		{
			for(j=step,i=n;j;j/=2)
				if(i-j>0 && a[i-j]>=val)
					i-=j;
			printf("%d\n",i);
    	}
	}
	fclose(stdout);
	return 0;
}