#include<fstream.h>
ifstream f("cautbin.in"); ofstream g("cautbin.out");
int n,i,T,m,p,u,tip,x,poz,a[100001];
int main()
{f>>n; for(i=1 ;i<=n; i++)f>>a[i]; 
 f>>T;
 while(T)
 {f>>tip>>x;
  p=1; u=n; poz=-1;
  if(tip<2)
	   {do	{m=(p+u)/2;
			  if(a[m]==x)
				  {poz=m; p=m+1;
				   while(p<=u)
					{m=(p+u)/2;
					 if(a[m]==x) {poz=m; p=m+1;} else u=m-1;
					}
				  }
				else if(a[m]<x) p=m+1; else u=m-1; 
			}
		while(p<=u); 
	    if(tip==1 && poz==-1) poz=u;
		g<<poz<<'\n';
	   }
	else
	   {do	{m=(p+u)/2;
			 if(a[m]==x)
				  {poz=m; u=m-1;
				   while(p<=u)
					{m=(p+u)/2;
					 if(a[m]==x) {poz=m; u=m-1;} else p=m+1;
					}
				  }
				else if(a[m]<x) p=m+1; else u=m-1; 
			}	 
		while(p<=u); 
		if(poz==-1) poz=p;
		g<<poz<<'\n';
	   }
  T--;
 }
 g.close(); return 0;
}