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