#include<fstream.h>
#define max 100002

long nr,a[max],poz;

void caut1(long st, long dr)
{
 long mijl;
	
 if (st<=dr)
	 {
	  mijl=(st+dr)/2;
	  if (a[mijl]==nr) /*daca nr se gaseste in mijloc*/
		 {
		  if (poz<mijl)
			  poz=mijl;
		  caut1(mijl+1,dr);
		 } else
		 if (nr<a[mijl])
			 caut1(st,mijl-1); else
			 caut1(mijl+1,dr);
	 }
}

void caut2(long st, long dr)
{
 long mijl;
	
 if (st<=dr)
	 {
	  mijl=(st+dr)/2;
	  if (a[mijl]<=nr)
		 {
		  if (poz<mijl)
			  poz=mijl;
		  caut2(mijl+1,dr);
		 } else
	     caut2(st,mijl-1); 
	 }
}

void caut3(long st, long dr)
{
 long mijl;
	
 if (st<=dr)
	 {
	  mijl=(st+dr)/2;
	  if (a[mijl]>=nr)
		 {
		  if (poz>mijl)
			  poz=mijl;
		  caut3(st,mijl-1);
		 } else
	     caut3(mijl+1,dr); 
	 }
}

int main()
{
 long i,m,op,n;
	
 ifstream fin("cautbin.in");
 ofstream fout("cautbin.out");
 fin>>n;
 for (i=1; i<=n; i++)
	 fin>>a[i];
 
 fin>>m;
 for (i=1; i<=m; i++)
	 {
	  fin>>op>>nr;
	  
	  if (op==0)
		  {
		   poz=0;
		   caut1(1,n);
		   fout<<poz<<'\n';
		  } else
	  if (op==1)
		  {
		   poz=0;
		   caut2(1,n);
		   fout<<poz<<'\n';
		  } else
		  {
		   poz=a[n]+1;
		   caut3(1,n);
		   fout<<poz<<'\n';
		  }
	 }	
	
 fin.close();
 fout.close();
 
 return 0;
}