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

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

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

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

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;
}