#include<fstream>
//#define dim 100001
using namespace std;
unsigned int a[100001];
int main()
{unsigned int n,m,nr,i,j,poz;
int x,ok=0;
  ifstream f("cautbin.in");
  ofstream g("cautbin.out");
 f>>n;
  for(i=1;i<=n;i++)
   f>>a[i];
 f>>m;
   for(i=1;i<=m;i++)
  {f>>x>>nr; j=0; ok=0;
    if(a[n/2]<nr)
     {j=n/2;
	  while(a[j]<=nr)
      {j++;	poz=j;}}
    if(a[n/2]>nr)
		while(a[j]<=nr)
          {j++; poz=j;}
	if(a[n/2]==nr) poz=n/2;	  
       
    if(a[poz]==nr)
      ok=1;
   
   if((x==0)&&(ok==1)) g<<poz<<'\n';
   if((x==0)&&(ok==0)) g<<"-1"<<'\n';
   
   if((x==1)&&(ok==0)) g<<poz-1<<'\n';
   if((x==1)&&(ok==1)) g<<poz<<'\n';
   
   if(x==2) g<<poz<<'\n';}

f.close();  
g.close();
return 0;
}