#include<stdio.h>
long  m,n,i,t,x,s,a[100010];
int cbt1(long x)
{
  long dr,st,m;
  dr=n;
  st=1;
  while(st<=dr)
  {
	m=(st+dr)/2;
	if(x>=a[m]) st=m+1;
	else dr=m-1;
  }
  st--;
  if(a[st]!=x) return -1;
  else return st;
}

int cbt2(long x)
{
  long dr,st,m;
  dr=n;
  st=1;
  while(st<=dr)
  {
	m=(st+dr)/2;
	if(x<=a[m]) dr=m-1;
	else st=m+1;
  }
  st--;
  return st;
}

int cbt3(long x)
{
  long dr,st,m;
  dr=n;
  st=1;
  while(st<=dr)
  {
	m=(st+dr)/2;
	if(x<=a[m]) dr=m-1;
	else st=m+1;
  }
  return st;
}

int main()
{
  freopen("cautbin.in","r",stdin);
  freopen("cautbin.out","w",stdout);

  scanf("%ld",&n);
  for(i=1;i<=n;++i)
	scanf("%ld",&a[i]);

  scanf("%ld",&m);
  for(i=1;i<=m;++i)
  {
	scanf("%ld%ld",&t,&x);
	if(t==0) s=cbt1(x);
	if(t==1) s=cbt2(x);
	if(t==2) s=cbt3(x);
	printf("%ld\n",s);
  }
  return 0;
}