#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(v[m]<=x)
             {st=m+1;b=m;}
     else
           dr=m-1; 
      }
}


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

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)
          {
          bs1(b);
          printf("%ld\n",b+1);
          }
        else
          {
          bs2(b);
          printf("%ld\n",b-1);
          }
        }
   }

return 0;
}