#include<cstdio>
void read(),solve();
int n,a[100010],x,c,m,i,ok;
long long st,dr,mid;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	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);
}
void solve()
{
	for(;m;m--)
	{
		scanf("%d%d",&c,&x);
		if(c==0)
		{
			ok=0;
			for(st=1,dr=n;st<=dr;)
			{
				mid=(st+dr)>>1;
				if(a[mid]==x&&a[mid+1]>x){ok=1;break;}
				if(a[mid]<=x)st=mid+1; else dr=mid-1;
			}
			if(ok)printf("%lld\n",mid); else printf("-1\n");
			continue;
		}
		if(c==1)
		{
			for(st=1,dr=n;st<=dr;)
			{
				mid=(st+dr)>>1;
				if(a[mid]<=x&&a[mid+1]>x)break;
				if(a[mid]<=x)st=mid+1; else dr=mid-1;
			}
			printf("%lld\n",mid);
			continue;
		}
		for(st=1,dr=n;st<=dr;)
		{
			mid=(st+dr)>>1;
			if(a[mid]>=x&&a[mid-1]<x)break;
			if(a[mid]<x)st=mid+1; else dr=mid-1;
		}
		printf("%lld\n",mid);
	}
}