#include <fstream.h>
ifstream f("cautbin.in");
ofstream g("cautbin.out");
long v[100001], n, m, i;
bool sw;

int zero (long k, long x, long y)
{
int xx, yy;
while (x<k)
	if (v[y/2]==k)
   	{
      xx=x;
      yy=y;
      if (zero(k, xx, yy)==-1)
         {
      	return y/2;
         break;
         }
      }
   else
   	if (v[y/2]<k)
      	y=y/2;
      else
      	x=y/2;
}

int unu (long k)
{
long x, y;
x=1;
y=n;
while (x<k)
   if (v[y/2]>=k&&v[y/2-1]<=k)
   	if (v[y/2]==k)
      	return y/2;
      else
      	return y/2-1;
   else
   	if (v[y/2]<k)
      	y=y/2;
      else
      	x=y/2;
}

int doi(long k)
{
long x, y;
x=1;
y=n;
while (x<k)
   if (v[y/2]>=k&&v[y/2-1]<=k)
   	if (v[y/2-1]==k)
      	return y/2-1;
      else
      	return y/2;
   else
   	if (v[y/2]<k)
      	y=y/2;
      else
      	x=y/2;
}

int main()
{
long k;
f>>n;
for (i=1;i<=n;i++)
	f>>v[i];
f>>m;
for (i=1;i<=m;i++)
	{
   f>>sw>>k;
   if (!sw)
   	g<<zero(k, 1, n)<<"\n";
   else
   	if (sw==1)
      	g<<unu(k)<<"\n";
      else
      	g<<doi(k)<<"\n";
   }
f.close();
g.close();
return 0;
}