#include<stdio.h>

#define max 100001

long x,y,n,m,i;
long v[max];



void cautarebinara0(long a,long b,long c)
{
while (a<=b)
{
c=(a+b)/2;
if (v[c]==y)
	   {
	   printf("%ld\n",c);
	   return;
	   }
	   if (v[c]<x) a=c+1;
		  else b=c-1;
	   }
if (v[c]==y)
	   {
	   printf("%ld\n",c);
	   return;
	   }
	   else printf("%ld\n",-1);
}



void cautarebinara1(long a,long b,long c)
{
while (a<b)
{
c=(a+b)/2;
if (v[c]<y) a=c+1;
       else b=c;
}
c=(a+b)/2;
if (v[c]>y) printf("%ld\n",c-1);
}






void cautarebinara2(long a,long b,long c)
{
while (a<b)
{
c=(a+b)/2;
if (v[c]<y) a=c+1;
       else b=c;
}
c=(a+b)/2;
if (v[c]<y) printf("%ld\n",c+1);
}




int main()
{
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);

scanf("%ld",&n);

for (i=1;i<=n;i++);

scanf("%ld",&v[i]);

scanf("%ld",&m);

for (i=1;i<=m;i++)
{
scanf("%ld %ld", &x, &y);

switch(x)
{
case 0:  {cautarebinara0(1,n,y);break;}
case 1:  {cautarebinara1(1,n,y);break;}
case 2:  {cautarebinara2(1,n,y);break;}
}
}
return 0;
}