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

int zero (long k)
{
bool swx=0;
long t, x, y;
x=1;
y=n;
while (x<k)
	if (v[(x+y)/2]==k)
   	{
      t=(x+y)/2+1;
		while (v[t]==k)
         {
         swx=1;
   		t++;
         }
      	return t-1;
      }
   else
   	if (v[(x+y)/2]>k)
      	y=(x+y)/2;
      else
      	x=(x+y)/2;
if (!swx)
	return -1;
}

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

int doi(long k)
{
long x, y;
x=1;
y=n;
while (x<k)
   if (v[(x+y)/2]>=k&&v[(x+y)/2-1]<=k)
   	if (v[(x+y)/2-1]==k)
      	return (x+y)/2-1;
      else
      	return (x+y)/2;
   else
   	if (v[(x+y)/2]>k)
      	y=(x+y)/2;
      else
      	x=(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)<<"\n";
   else
   	if (sw==1)
      	g<<unu(k)<<"\n";
      else
      	g<<doi(k)<<"\n";
   }
f.close();
g.close();
return 0;
}