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


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;
  }
return st;
}


long bs2(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(x==0)
  if(v[st-1]!=val)
	 return 0;
return st;
}


void read()
{
freopen("cautbin.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",bs2(val)-1);
  if(x==1)
	 printf("%ld\n",bs1(val)-1);
  if(x==2)
	 printf("%ld\n",bs2(val));
  }
}


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