#include <stdio.h>
int a[100001],n,m;
int bin1(int nr)
{ int lo=1,hi=n,mid;
	while(lo<=hi)
     { mid=lo+(hi-lo)/2;

	 if(nr<a[mid]) hi=mid-1;
	else if(nr>a[mid])lo=mid+1;
	if(a[mid]==nr)
		return mid;
	     }
 return -1;
}
int bin2(int nr)
{ int lo=1,hi=n,mid,nr2=0;
	while(lo<=hi)
	{ mid=lo+(hi-lo)/2;
	 if(nr>=a[mid]) nr2=mid,lo=mid+1;
	 else hi=mid-1;

	}
   return nr2;
}
int bin3(int nr)
{ int lo=1,hi=n,mid,nr2=n+1;
	while(lo<=hi)
	{ mid=lo+(hi-lo)/2;
	if(nr<=a[mid]) nr2=mid,hi=mid-1;
	else lo=mid+1;
	}
   return nr2;
   }
int main()
{  int b,x,i;
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(i=1;i<=m;i++)
	{scanf("%d %d", &b,&x);
	 if(b==0) printf("%d\n",bin1(x));
	 else if(b==1) printf("%d\n",bin2(x));
	 else printf("%d\n",bin3(x));}
return 0;
}