#include<fstream.h>
ifstream f("cautbin.in"); 
ofstream g("cautbin.out");
int n,i,nr,m,p,u,intr,x,poz;
int a[100001];
int main()
{f>>n;
 for(i=1 ;i<=n; i++) f>>a[i]; 
 f>>nr;
 while(nr!=0)
 {f>>intr>>x;
  p=1; u=n; poz=-1;
  if(intr<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(intr==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';
	   }
  nr--;
 }
 g.close(); return 0;
}