#include<stdio.h>
long n,m,x;
long v[100010];


long bs0(long val)
{
long st,dr,m;
st=1;
dr=n;
while(st<=dr)
  {
  m=(st+dr)>>1;
  if(val>=v[m])
	 st=m+1;
  else
	 dr=m-1;
  }
if(v[st-1]!=val)
  return -1;
return st-1;
}


long bs1(long val)
{
long st,dr,m;
st=1;
dr=n;
while(st<=dr)
  {
  m=(st+dr)>>1;
  if(val<=v[m])
	 dr=m-1;
  else
	 st=m+1;
  }
if(v[st]>val)
  st--;
if(st==n+1)
  st--;
return st;
}


long bs2(long val)
{
long st,dr,m;
st=1;
dr=n;
while(st<=dr)
  {
  m=(st+dr)/2;
  if(val>=v[m])
	 st=m+1;
  else
	 dr=m-1;
  }
if(v[st-1]==val)
  return st-1;
return st;
}


void read()
{
freopen("cautbin1.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%ld",&n);
long i,val;
for(i=1;i<=n;i++)
  scanf("%ld",&v[i]);
scanf("%ld",&m);
for(i=1;i<=m;i++)
  {
  scanf("%ld%ld",&x,&val);
  if(x==0)
	 printf("%ld\n",bs0(val));
  else
	 if(x==1)
		printf("%ld\n",bs1(val));
	 else
		printf("%ld\n",bs2(val));
  }
}


int main()
{
read();
return 0;
}