#include<stdio.h>

long n,m,b,v[100000];

void read()
{
long i;
scanf("%ld",&n);
for(i=1;i<=n;++i)
   scanf("%ld",&v[i]);
}

long bs0(long x)
{
long st,dr,m;
st=1;
dr=n;
while(st<=dr)
     {
     m=(st+dr)>>1;
     if(v[m]==x)
       return m;
     else
        {
        if(v[m]<x)
           st=m+1;
        else
             dr=m-1;
        }
     }
return -1;
}

void bs1(long x)
{
long st,dr,m;
st=1;
dr=n;
while(st<=dr)
     {
     m=(st+dr)>>1;
     if(x<=v[m])
           dr=m-1;
     else
           {st=m+1;b=m;}
     }
}


void bs2(long x)
{
long st,dr,m;
st=1;
dr=n;
while(st<=dr)
     {
     m=(st+dr)>>1;
     if(x>=v[m])
            st=m+1;
           
     else
            {dr=m-1;b=m;}
     }
return m;
}

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

long i;
int a;

read();

scanf("%ld",&m);

for(i=1;i<=m;++i)
   {
   scanf("%d%ld",&a,&b);
   if(a==0)
     {
     b=bs0(b);
     printf("%ld\n",b);
     }
     else
        {
        if(a==1)
          {
          b=bs1(b);
          printf("%ld\n",b);
          }
        else
          {
          b=bs2(b);
          printf("%ld\n",b);
          }
        }
   }

return 0;
}